小A的柱状图

题目描述

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],

现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。

输入描述:

一行一个整数N，表示长方形的个数
接下来一行N个整数表示每个长方形的宽度
接下来一行N个整数表示每个长方形的高度

输出描述:

一行一个整数，表示最大的矩形面积

题解

面积最大的矩形肯定是以x坐标轴为一条边的矩形

那么对于每个点，我们求出其向左最多可以扩展到哪个点以及向右最多可以扩展到哪个点，对于每个点所形成的矩形我们取一个最大值即可。

怎么求出其向左向右最大的扩展范围呢？

我们利用单调栈去求取。

单调栈解决的是以某个值为最小（最大）值的最大区间，实现方法是：求最小值（最大值）的最大区间，维护一个递增（递减）的栈，当遇到一个比栈顶小的值的时候开始弹栈，弹栈停止的位置到这个值的区间即为此值左边的最大区间；同时，当一个值被弹掉的时候也就意味着比它更小（更大）的值来了，也可以计算被弹掉的值得右边的最大区间。

对于一个点可以向左扩展最多的点与该点之间的高度都要大于该点，故我们用单调栈维护，当栈顶元素的高度大于当前元素时，我们直接把它弹出栈，直到找到高度比它小的点为止。维护向右扩展的时候同理。

代码

/*
* Coder: niiii
* Language: cpp
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+100;
const int mod=1e9+7;
ll a[N],h[N],l[N],r[N];
stack<int> q;
int main(){
    ios::sync_with_stdio(false);
    int n;
    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];
    for(int i=1;i<=n;++i){
        while(!q.empty()&&h[q.top()]>h[i])q.pop();
        if(!q.empty())l[i]=q.top();
        else l[i]=0;
        q.push(i);
    }
    while(!q.empty())q.pop();
    for(int i=n;i>=1;--i){
        while(!q.empty()&&h[q.top()]>h[i])q.pop();
        if(!q.empty())r[i]=q.top()-1;
        else r[i]=n;
        q.push(i);
    }
    ll ans=0;
    for(int i=1;i<=n;++i){
        ans=max(ans,(a[r[i]]-a[l[i]])*h[i]);
    }
    cout<<ans<<endl;
}

看到有大佬用笛卡尔树去做了，有空我也学学再补充此方法