题解 | #小A的柱状图#

思路

枚举每个矩形，求出该矩形向左右两侧延伸能得到的最大矩形面积：res_i
答案就是 max(res_1,res_2,...,res_n)

代码中一些变量的解释：
l[i]：矩形 i 的左边界：从 i 向左延伸，第一个比其高度小的矩形位置
r[i]：同理

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6+10;

int l[N],r[N];
int a[N],h[N];
int stk[N];
int hh,n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=n;i++) cin>>h[i];

    stk[++hh]=0;
    for(int i=1;i<=n;i++){
        while(hh&&h[i]<=h[stk[hh]]) hh--;
        l[i]=stk[hh];
        stk[++hh]=i;
    }

    hh=0;
    stk[++hh]=n+1;
    for(int i=n;i>=1;i--){
        while(hh&&h[i]<=h[stk[hh]]) hh--;
        r[i]=stk[hh];
        stk[++hh]=i;
    }

    ll res=-1;
    for(int i=1;i<=n;i++) res=max(res,(ll)h[i]*(a[r[i]-1]-a[l[i]]));
    cout<<res<<endl;

    return 0;
}