题解 | #小A的柱状图#

对于每一个元素，在栈中向右找到小于等于当前元素的元素，在找元素的过程中计算以途径的元素为高，以已经经过的宽度为底的矩形的面积，找出最大面积

using namespace std;
typedef long long ll;
ll idx=0,n,ans=0;
const int N=1e6+10;
ll h[N],s[N],w[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i]+=w[i-1];//前缀和，方便计算宽度
    }
    for(int i=1;i<=n;i++) cin>>h[i];
    h[n+1]=0;//在栈顶加上0，防止最后栈中有元素没有被弹出
    n++;
    for(int i=1;i<=n;i++)
        if(h[i]>=h[s[idx]]) s[++idx]=i;
    else{
        while(idx&&h[s[idx]]>h[i]){//当不符合条件时不断弹出栈顶并计算面积
            int k=s[idx--];
            ans=max(ans,(w[i-1]-w[s[idx]])*h[k]);//w数组是宽度的前缀和，w[i-1]-w[s[idx]]即为当前矩形的宽度
        }
        s[++idx]=i;
    }
    cout<<ans;
}