P2659 美丽的序列 (单调栈)

P2659 美丽的序列 (单调栈)

题目链接

Solution

直接考虑单调栈处理出每一个点作为最小值的区间长度.
然后 \(O(n)\) 找一遍最大值即可. 记得开 long long,以及要注意 \(0\) 的问题.

Code

#include<bits/stdc++.h>
#define ll long long
#define N 2000001
#define in(x) x=read()
using namespace std;ll n,a[N];
ll L[N],R[N],sta[N],top;ll read()
{char ch=getchar();ll f=1,w=0;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}return f*w;
}int main()
{in(n);for(ll i=1;i<=n;i++) in(a[i]);for(ll i=1;i<=n;i++){if(a[i]==0){L[i]=i;continue;}if(a[sta[top]]<a[i]){sta[++top]=i,L[i]=i-1;continue;}while(a[sta[top]]>=a[i])top--;L[i]=sta[top]; sta[++top]=i;}top=0;for(ll i=n;i>=1;i--){if(a[i]==0){R[i]=i;continue;}if(a[sta[top]]<a[i]){sta[++top]=i,R[i]=i+1;continue;}while(a[sta[top]]>=a[i])top--;R[i]=sta[top]; if(top==0)R[i]=n+1;sta[++top]=i;}ll ans=0;for(ll i=1;i<=n;i++)//cout<<L[i]<<' '<<R[i]<<endl;ans=max(ans,a[i]*(R[i]-L[i]-1));cout<<ans<<endl;}

转载于:.html