codeforces 547B【单调栈】

题意： 有一个长度为n的序列，序列有长度为1...n的连续子序列， 一个连续子序列里面最小的值称作这个子序列的子序列的strength， 要求出每种长度的连续子序列的最大的strength。 思路： 以当前位置为最小值，向两边延伸。 那我就能知道这个位置作为最小值时长度。

具体思路忘了。。。 给出几组数据希望能有启发？

/* 10 1 2 3 4 5 4 3 2 1 6 10 100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 10 1 2 3 4 5 6 7 8 9 10 */ #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=2e5+10; struct asd { int left,right,w; }; int num[N],n,h[N]; stack<asd>q; int main() { asd now,nex; int temp,tmp; while(!q.empty()) q.pop(); memset(num,0,sizeof(num)); scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&h[i]); num[1]=max(num[1],h[1]); now.left=1; now.right=1; now.w=h[1]; q.push(now); bool flag; for(int i=2; i<=n; i++) { now.left=1; now.right=1; now.w=h[i]; while(!q.empty()&&q.top().w>h[i]) { nex=q.top(); q.pop(); now.left+=nex.left; temp=nex.right+nex.left-1; num[temp]=max(num[temp],nex.w); if(!q.empty()) q.top().right+=nex.right; } q.push(now); } flag=false; while(!q.empty()) { nex=q.top(); q.pop(); temp=nex.right+nex.left-1; num[temp]=max(num[temp],nex.w); if(!q.empty()) q.top().right+=nex.right; } temp=num[n]; for(int i=n;i>=1;i--) { if(num[i]<=temp) num[i]=temp; else temp=num[i]; } for(int i=1;i<=n;i++) printf("%d ",num[i]); return 0; }