单调栈+前缀和 || Nowcoder || 牛客小白月赛13 || 小A的柱状图

佚名 6年前 (2019-04-15) 随笔 1572人围观抢沙发百度已收录

题解：无

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define ll long long
 5 #define max(a,b) ((a)>(b)?(a):(b))
 6 using namespace std;
 7 inline ll rd(){
 8     ll x=0;char c=getchar();
 9     while(c<'0'||c>'9'){c=getchar();}
10     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
11     return x;
12 }
13 const ll maxn=(1e6)+50;
14 ll N,A[maxn],H[maxn],sig[maxn],S[maxn],L[maxn],R[maxn],top,ans;
15 //前缀和维护A[i] 
16 //用两个单调栈，分别从左往右和从右往左找出第一个小于H[i]的数的位置
17 int main(){
18     N=rd();
19     for(int i=1;i<=N;i++){
20         A[i]=rd();
21         sig[i]=sig[i-1]+A[i];
22     }
23     for(int i=1;i<=N;i++){
24         H[i]=rd();
25         ans=max(ans,A[i]*H[i]);
26     }
27     top=1;S[top]=1;L[1]=0;
28     for(int i=2;i<=N;i++){
29         while(top>=1&&H[S[top]]>=H[i])top--;
30         L[i]=S[top];
31         S[++top]=i;
32     }
33     top=1;S[top]=N;R[N]=0;
34     for(int i=N-1;i>=1;i--){
35         while(top>=1&&H[S[top]]>=H[i])top--;
36         R[i]=S[top];
37         if(R[i]==0)R[i]=N+1;
38         S[++top]=i;
39     }
40     for(int i=1;i<=N;i++)
41         ans=max(ans,(sig[R[i]-1]-sig[L[i]])*H[i]);
42     printf("%lld\n",ans);
43     return 0;
44 }