长度为n的一个数列
定义 一个区间内的 最小的值为 这个区间的strength
求长度为 1-n 的区间 最大的strength
先求出每个位置左边/右边 的比它小的值的位置
这样在 L+1 R-1 区间内这个位置是最小值
然而 区间[len]的值是小于等于区间[len-1]
即可以推出
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAXN = 200009;//点数的最大值
- const int MAXM = 604000;//边数的最大值
- const LL INF = 1<<30;
- const LL mod= 1000000007;
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- int low[MAXN],hig[MAXN],a[MAXN],ans[MAXN];
- int main()
- {
- int n;
- cin>>n;
- stack<int>st;
- for(int i=1;i<=n;i++)
- {
- ans[i]=0;
- cin>>a[i];
- }
- while(!st.empty()) st.pop();
- for(int i=1;i<=n;i++)
- {
- while(!st.empty()&&a[st.top()]>=a[i])
- st.pop();
- if(st.empty()) low[i]=0;
- else low[i]=st.top();
- st.push(i);
- }
- while(!st.empty()) st.pop();
- for(int i=n;i>=1;i--)
- {
- while(!st.empty()&&a[st.top()]>=a[i])
- st.pop();
- if(st.empty()) hig[i]=n+1;
- else hig[i]=st.top();
- st.push(i);
- }
- for(int i=1;i<=n;i++)
- {
- int len=hig[i]-low[i]-1;
- ans[len]=max(ans[len],a[i]);
- }
- ans[n+1]=0;
- for(int i=n;i>=0;i--)
- ans[i]=max(ans[i],ans[i+1]);
- for(int i=1;i<=n;i++)
- printf("%d ",ans[i]);
- return 0;
- }