长度为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; }