Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.
A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strengthof a group is the minimum height of the bear in that group.
Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.
InputThe first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.
The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.
OutputPrint n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.
Sample test(s) input10 1 2 3 4 5 4 3 2 1 6output
6 4 4 3 3 2 2 1 1 1
題目大意：
給出n個數，這n個數在區間長度為i（1~n）的時候可以分割成一些區間，這每個區間都會有一個最小值，在同樣長度的這些區間的最小值中，輸出最大值。
思路：利用單調棧，保持棧內單調遞增。
單調棧：單調棧是以某一個值為最大（最小）值，向兩個方向進行延伸，如果兩邊的數比他大（小），就進行延伸。並且利用棧可以使時間復雜度控制在O（n）。
#include#include #include #include #include #define LL __int64 using namespace std; struct node{ LL num,pre,next; }; //代表數字，前驅有幾個，後繼有幾個。 LL max(LL a,LL b){ return a>b?a:b; } LL a[200005],ans[200005]; int main() { LL n,i,j; while(scanf(%I64d,&n)!=EOF) { stack Q; node tmp; memset(ans,0,sizeof(ans)); //ans數組記錄i范圍時的最大數字。 for(i=1;i<=n;i++) { scanf(%I64d,&a[i]); } tmp.num=a[1]; tmp.pre=tmp.next=1; Q.push(tmp); for(i=2;i<=n;i++) { node tmp1; tmp1.num=a[i]; tmp1.pre=tmp1.next=1; while(!Q.empty()&&Q.top().num>=tmp1.num) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; tmp1.pre+=tmp.pre; LL l=tmp.pre+tmp.next-1; //記錄長度 ans[l]=max(ans[l],tmp.num); //比較長度為l 的ans大小。 } Q.push(tmp1); } while(!Q.empty()) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; LL l=tmp.pre+tmp.next-1; ans[l]=max(ans[l],tmp.num); } for(i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); //最後還要更新一下，可能中間有些長度沒有被更新到。而且可以斷定ans[i+1]>ans[i]一定成立。 for(i=1;i
