input
101 2 3 4 5 4 3 2 1 6
output
6 4 4 3 3 2 2 1 1 1 题意：给出n个数，这n个数在区间长度为i（1~n）的时候可以分割成一些区间，这每个区间都会有一个最小值，，在同样长度的这些区间的最小值中，输出最大值思路：使用单调栈，保持栈内的数的单调递增性#include <iostream>#include <stdio.h>#include <string.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <bitset>#include <algorithm>#include <climits>using namespace std;#define LS 2*i#define RS 2*i+1#define UP(i,x,y) for(i=x;i<=y;i++)#define DOWN(i,x,y) for(i=x;i>=y;i–)#define MEM(a,x) memset(a,x,sizeof(a))#define W(a) while(a)#define gcd(a,b) __gcd(a,b)#define LL long long#define N 200005#define MOD 1000000007#define INF 0x3f3f3f3f#define EXP 1e-8#define lowbit(x) (x&-x)/*num栈顶的元素，width宽度，跟现在入栈的数之间相隔了多少个数，因为要求的是连续区间，所以这个也是必须记录的*/struct node{int num,width;node() {};node(int _num,int _width):num(_num),width(_width) {}};stack<node> S;int a[N],ans[N];int main(){int n,i,j;scanf("%d",&n);for(i = 0; i<n; i++)scanf("%d",&a[i]);a[n++] = 0;MEM(ans,0);for(i = 0; i<n; i++){int len = 0;//连续区间的长度node k;while(!S.empty()){k = S.top();if(k.num<a[i])break;//新入栈的元素比栈顶元素要小，那么对于这个连续区间而言，这个比新入栈的元素就没有用了，可以出栈int ls=k.width+len;//出栈的同时获得其长度if(k.num>ans[ls])//ans记录ls区间的时候的最大值{ans[ls]=k.num;}len+=k.width;S.pop();}S.push(node(a[i],len+1));}for(i = n-1; i>=1; i–)//因为上面只更新了一部分的点，所以现在要对那些没有更新的点也更新ans[i]=max(ans[i],ans[i+1]);printf("%d",ans[1]);for(i = 2; i<n; i++)printf(" %d",ans[i]);printf("\n");return 0;}
而是深沉的意志恢弘的想象炙热的恋情；青春是生命的深泉在涌流。
