每日一题 小A的柱状图 (单调栈)

一.题意

给出 n 个小长方形的宽度和高度，求最大的矩形面积。

二.题解

先谈谈经典的单调栈模板题的解法，给出高度且宽度恒为1，求最大的矩形面积。
用单调栈维护每个点左边第一个比自己矮的矩形和右边第一个比自己矮的矩形，得到 r 数组和 l 数组。
那么 ~ 之间的矩形中最矮的就是 ，即以当前矩形为最矮矩阵的面积为:

遍历枚举即可得到最大的矩形面积:

考虑宽度不恒为 1， 只是对最后答案的计算出现了影响，用前缀和维护 1 ~ i 的宽度和:

依然可以通过遍历枚举得到最大的矩形面积:

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=5e2+5;
const int mod=1e9+7;

ll s[manx],l[manx],r[manx];
ll h[manx],w[manx];
ll n,top;

int main(){
    io; 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];
    top=0; 
    for(int i=1;i<=n;i++){
        while(top&&h[s[top]]>=h[i]) --top;
        if(top) l[i]=s[top];
        else l[i]=0;
        s[++top]=i;
    }
    top=0;
    for(int i=n;i>=1;i--){
        while(top&&h[s[top]]>=h[i]) --top;
        if(top) r[i]=s[top];
        else r[i]=n+1;
        s[++top]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++) 
        ans=max(ans,(w[r[i]-1]-w[l[i]])*h[i]);
    cout<<ans<<endl;
    return 0;
}