Description
Today is Christmas day. There are n single boys standing in a line. They are numbered form 1 to n from left to right. The i-th single boy has ai single strength. They are singing single boy Christmas song! Single boy,single boy, single all the way, having party together and turning into gay! Hey! A group of single boys is non-empty contiguous segment of the line. The size of a group is the number of single boys in that group. The single strength of a group is the minimum single strength of the single boy in that group. Now we want to know for each x such that 1<=x<=n the maximum single strength among all groups of size x.
Input
The first line of input contains T(<=30), the test cases. For each test case, the first line is a integer n(1 <= n <= 2*10^5), the number of single boys. The second line contains n integers [1,10^9] separated by space, the single strength of each single boy.
Output
Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.
Sample Input
1 10 1 2 9 3 8 2 2 10 19 6
Sample Output
19 10 6 2 2 2 2 2 2 1
题意：n个数,(1<=k<=n),在n个数中连续的k个数为一个区间长度，一共有n-k+1个区间，
每个区间选出区间中的最小值min[j](1<=j<=n-k+1)，然后在n-k+1个区间中选出最大的
min[j],得到max[i](1<=i<=k),然后按k=1~n顺序输出max[i].
由于数据太大，暴力模拟寻找太慢不能实现，所以我们想到的是求 以num[i]为最小值
的区间长度，然后选择区间长度相等Max(num[i]),开始我用了暴力寻找区间，由于数据
太大，TLE了，后来学习别人方法，用栈求得区间长度，我们把以num[i]为最小值的区间
的左右边界求出来，右边界-左边界就是区间长度；
用栈求区间左右边界：先求左边界后求右边界，开始将下标0入栈，我们的数组是从1
开始的，然后比较以栈顶元素为下标的值是否大于等于当前值，是的话出栈，直到比当前
值小，当前值的左边界就等于当前下标-栈顶元素+1，最后每次都要把当前下标入栈，
求右边界完全一样。
#include <iostream> #include <stdio.h> #include <string.h> #include <stack> using namespace std; const int maxn=3000000; struct ac { int num; int l,r; }d[maxn]; int ans[maxn]; stack<int>sta; int main() { int t,n,Top,dn; scanf("%d",&t); while(t--) { int flag=0; scanf("%d",&n); d[0].num=0;///以0 ，n+1为下标的值为0. d[n+1].num=0; sta.push(0);///压入0下标 for(int i=1; i<=n; i++) { scanf("%d",&d[i].num); while(!sta.empty())///求左边界 { Top=sta.top(); if(d[Top].num>=d[i].num)///比较当前值与以栈顶元素为下标的值 sta.pop(); else break; } Top=sta.top(); d[i].l=Top+1;///左边界 sta.push(i);///每次压入当前下标 } while(!sta.empty()) sta.pop(); sta.push(n+1);///求右边界，压入下标n+1 for(int i=n; i>=1; i--) { while(!sta.empty()) { Top=sta.top(); if(d[Top].num>=d[i].num) sta.pop(); else break; } Top=sta.top(); d[i].r=Top-1; sta.push(i); } while(!sta.empty()) sta.pop(); memset(ans,0,sizeof(ans)); for(int i=1; i<=n; i++)///求ans，每次都更新 以区间长度为dn的最大值 { dn=d[i].r-d[i].l+1; ans[dn]=max(ans[dn],d[i].num); } 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]); printf(" "); } return 0; }
样例值 1 2 9 3 8 2 2 10 19 6
以该值为最
小值的区间长度 10 9 1 3 1 9 9 2 1 3
区间长度为 10有1 ,max[10]=1;
区间长度为 9 有2,2,2,max[9]=2;
区间长度为 4-8 都没有，即为0,那么以区间为长度为9的更新max[4-8]=2;
区间长度为 3有 3,6, max[3]=6;
区间长度为 2有 10, max[2]=10;
区间长度为 1有 9,8,19,max[1]=19;
为什么以区间更大的修改，以为区间越大，数值越小，区间小的的最大值不可能大于
区间大的最大值