本文共 1194 字，大约阅读时间需要 3 分钟。
题意：
思路：
单调栈题。求出以每个数为区间最大值的区间范围即可。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 typedef long long ll;13 typedef pair pll;14 const int INF = 0x3f3f3f3f;15 const int maxn = 2*1e5+5;16 17 int n;18 int a[maxn];19 int sta[maxn];20 int l[maxn], r[maxn];21 int ans[maxn];22 23 int main()24 {25 //freopen("in.txt","r",stdin);26 while(~scanf("%d",&n))27 {28 memset(ans,0,sizeof(ans));29 for(int i=1;i<=n;i++) scanf("%d",&a[i]);30 int top = 0;31 for(int i=1;i<=n;i++)32 {33 while(top && a[sta[top]]>=a[i]) top--;34 if(top==0) l[i]=1;35 else l[i]=sta[top]+1;36 sta[++top]=i;37 }38 top = 0;39 for(int i=n;i>=1;i--)40 {41 while(top && a[sta[top]]>a[i]) top--;42 if(top==0) r[i]=n;43 else r[i]=sta[top]-1;44 sta[++top]=i;45 }46 for(int i=1;i<=n;i++)47 ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],a[i]);48 for(int i=n-1;i>=1;i--)49 ans[i]=max(ans[i],ans[i+1]);50 for(int i=1;i<=n;i++)51 printf("%d%c",ans[i],i==n?'\n':' ');52 }53 return 0;54 }
转载于:https://www.cnblogs.com/zyb993963526/p/7634149.html
