链接：https://ac.nowcoder.com/acm/contest/22669/Q

来源：牛客网

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i],每个矩形的高度是h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。

虽然是道单调栈模板题，但是我依旧花了好久调试。对于每个柱形，我们只需要找到它能到达的最左端点和最右端点，即可计算出以该柱形为高时所组成的矩形面积。其中的宽度差值用前缀和求解即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n;
    cin>>n;
    int wide[n+1];
    wide[0]=0;  //为前缀和准备
    int high[n+1];
    int l[n+1];//存储每个柱能走到的最左端点
    int r[n+1];//存储每个柱能走到的最右端点
    int res=0;
    for(int i=1;i<=n;i++) {
        cin>>wide[i];
        wide[i]+=wide[i-1];
    }
    for(int i=1;i<=n;i++) cin>>high[i];
    stack<int> t;

    //寻找每个柱能走到的最左端点
    for(int i=1;i<=n;i++){
        while(!t.empty()&&high[i]<=high[t.top()]) t.pop();
        if(t.empty()) l[i]=0;  //能到达最左端
        else l[i]=t.top();
        t.push(i);
    }

    while(!t.empty()) t.pop();//清空

    //寻找每个柱能走到的最右端点
    for(int i=n;i>=1;i--){
        while(!t.empty()&&high[i]<=high[t.top()]) t.pop();
        if(t.empty()) r[i]=n;  //能到达最右端
        else r[i]=t.top()-1;//注意这个地方的索引值应该是要-1，因为这个柱子到不了栈顶端点
        t.push(i);
    }
    for(int i=1;i<=n;i++){
          res=max(res,high[i]*(wide[r[i]]-wide[l[i]]));//用前缀和求解最优矩形
    }
    cout<<res;
}
signed main()
{
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}