51nod-1437 迈克步(单调栈)
原题链接
收藏 
关注 有n只熊。他们站成一排队伍，从左到右依次1到n编号。第i只熊的高度是ai。
一组熊指的队伍中连续的一个子段。组的大小就是熊的数目。而组的力量就是这一组熊中最小的高度。
迈克想知道对于所有的组大小为x（1 ≤ x ≤ n）的，最大力量是多少。
Input
单组测试数据。 第一行有一个整数n (1 ≤ n ≤ 2×10^5)，表示熊的数目。 第二行包含n个整数以空格分开，a1, a2, ..., an (1 ≤ ai ≤ 10^9),表示熊的高度。
Output
在一行中输出n个整数，对于x从1到n，输出组大小为x的最大力量。
Input示例
10 1 2 3 4 5 4 3 2 1 6
Output示例
6 4 4 3 3 2 2 1 1 1
遍历每个元素num[i]求出以这个元素为最小值的最大区间,长度d, 更新ans[d] = max(ans[d], num[i]), 最从尾到头更新ans[i], ans[i] = max(ans[i], ans[i+1])
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
using namespace std;
typedef long long ll;int Stack1[maxn], Stack2[maxn], num[maxn], ans[maxn], len[maxn];
int get_int(){int m = 0;char ch = getchar();while(ch >= '0' && ch <= '9'){m = m * 10 + ch - '0';ch = getchar();}return m;
}
int main(){// freopen("in.txt", "r", stdin);int n;scanf("%d", &n);getchar();for(int i = 0; i < n; i++){num[i] = get_int();}Stack1[0] = 0;len[0] = 0;int j = 1;for(int i = 1; i < n; i++){while(j && num[Stack1[j-1]] >= num[i]){j--;}if(j == 0)len[i] = 0;elselen[i] = Stack1[j-1] + 1;Stack1[j++] = i;} j = 1;Stack2[0] = n - 1;len[n-1] = n - 1 - len[n-1] + 1;for(int i = n - 2; i >= 0; i--){while(j && num[Stack2[j-1]] >= num[i]){j--;}if(j == 0)len[i] = n - 1 - len[i] + 1;elselen[i] = Stack2[j-1] - len[i];int d = len[i];ans[d] = max(ans[d], num[i]);Stack2[j++] = i;}ans[len[n-1]] = max(ans[len[n-1]], num[n-1]);for(int i = n - 1; i >= 1; i--){if(ans[i] < ans[i+1])ans[i] = ans[i+1];}printf("%d", ans[1]);for(int i = 2; i <= n; i++)printf(" %d", ans[i]);puts("");return 0;
}