【每日一题】小A的柱状图

题目

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

解题思路

如果使用暴力方法，那么需要枚举宽或枚举高。

• 如果枚举宽度，那么需要使用双重循环枚举矩形的左右边界固定宽 ，确定高度 ，求面积 。时间复杂度 。
• 如果枚举高度，可以使用一重循环枚举某一根柱子，将其固定为矩形的高度 。随后从这跟柱子开始向两侧延伸，直到遇到高度小于 的柱子，就确定了矩形的左右边界（不包括边界本身）。时间复杂度 。

可以根据上述枚举高度的暴力方法进行优化。

先确定一根柱子，求出这根柱子左侧最近的小于其高度的柱子，即为左边界。

在遍历高度时，同时维护一个递增的单调栈。栈中存储柱子的下标和高度。

• 如果栈为空，表示当前柱子的左边不存在比它还矮的柱子，记它的左边界为 -1。
• 如果栈顶的元素的高度大于等于当前柱子高度，那么这个栈顶元素对于求后面柱子的左边界没有作用，故将其弹出，压入当前下标。
  这么做的原因是：从后面的柱子向左延伸时，当前柱子会将左边柱子挡住。

确定一根柱子的右边界也按照上述方法。
最后，遍历高度 ，根据其左右边界确定宽度 ，其面积为 ，更新最大面积 。返回结果。时间复杂度为 。

对于求柱子的右边界可以再优化一下。
当位置 被弹出栈时，说明此时遍历到的位置 的高度小于等于 ，并且在 与 之间没有其他高度小于等于 的柱子。所以位置 就是位置 的右边界。
这样，一遍遍历就可以求出每根柱子的左右边界。

C++代码

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> p(N), h(N);
    int wide = 0;
    for(int i=0; i<N; ++i){
        cin >> p[i];
        if(i>0)
            p[i] += p[i-1];
    }
    for(int i=0; i<N; ++i)
        cin >> h[i];

    vector<int> left(N,-1), right(N,N);
    stack<int> sta;
    for(int i=0; i<N; ++i){
        while(!sta.empty() && h[sta.top()] >= h[i]){
            right[sta.top()] = i;
            sta.pop();
        }
        if(sta.empty())
            left[i] = -1;
        else
            left[i] = sta.top();
        sta.push(i);
    }

    long long ans = 0, w;
    for(int i=0; i<N; ++i){
        if(left[i]==-1)
            w = p[right[i]-1];
        else
            w = p[right[i]-1] - p[left[i]];
        ans = max(ans, h[i]*w);
    }

    cout << ans << endl;
    return 0;
}