小A的柱状图

题目链接
小A的柱状图
题意
这是一个简单的单调栈问题，对于每一个矩形我们可以找出其能够到达的最远位置，所以只需要枚举n个矩形的最大值就ok啦~

#include<bits/stdc++.h>
typedef long long ll;
const int maxn =1e6+5;
using namespace std;
int n,height[maxn],wid[maxn],le[maxn],ri[maxn],b[maxn];//he代表每个矩形的高度，b代表每个矩形的宽度，wid是从1到第i个矩形的总宽度，le ri能到达最左或者最右的第几个矩形 
stack<int>q;
long long ans =0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        wid[i]=wid[i-1]+b[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>height[i];
    }
    for(int i=1;i<=n;i++)//找每个矩形能到达最左 
    {
        while(!q.empty()&&height[q.top()]>=height[i]) q.pop();
        if(q.empty()) le[i]=1;
        else le[i]=q.top()+1;
        q.push(i);
    }
    while(!q.empty()) q.pop();//一定要清栈剩余元素 
    for(int i=n;i>=1;i--) //找每个矩形能到达最右 
    {
        while(!q.empty()&&height[q.top()]>=height[i]) q.pop();
        if(q.empty()) ri[i]=n;
        else ri[i]=q.top()-1;
        q.push(i);
    }
    for(int i=1;i<=n;i++) //找最大值 
    {
        ans =max (ans,(1LL)*(wid[ri[i]]-wid[le[i]-1])*height[i]);
    }
    cout<<ans<<endl;
    return 0;
}