题目内容

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例

输入: [2,1,5,6,2,3]
输出: 10

题解

本题考查单调栈算法。

首先，单调栈可以用于寻找比最靠近目标值小或者大的数。这里我们需要单调栈帮我们寻找这样的数字，用于枚举每个主柱子对应的矩形面积。

然后，想法就是，枚举每个柱子可以产生的最大面积的矩形，找到最优解。具体来说，就是以每个柱子的上边界为顶，寻找左右两边第一个比目标柱子矮的柱子为对应矩形的左右边界，然后求其面积寻找全局最大的矩形面积即可。

单调栈的具体做法，请见公号之前的基础算法系列的文章介绍，这里不解释了。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        //单调栈，枚举以每个柱子的高度为上边界，看左边界和右边界的情况，也是去看左边第一个比该柱子矮的柱子和右边第一个比这个柱子矮的柱子，这样就能求出对应的矩形的面积，然后找出一个全局最大即可。
        int n = h.size();
        vector<int> left(n), right(n);
        stack<int> stk;

        for (int i = 0; i < n; i ++ ) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();
        for (int i = n - 1; i >= 0; i -- ) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            res = max(res, h[i] * (right[i] - left[i] - 1));
        }

        return res;
    }
};