Leetcode 84.柱状图中最大的矩形

题目描述：

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

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

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

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

示例:

1
2

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

链接：

https://leetcode-cn.com/problems/largest-rectangle-in-histogram

题目分析

  通过观察我们可以知道，对于每一个柱子，都有以它为高的矩形存在，我们只需要遍历所有这样的矩形即可得到最大矩形。每一个矩形的宽边界是哪里呢？是这个柱子两边低于它的第一个柱子。获取这个信息并不需要每次都进行遍历，我们只需要使用单调栈的做法。按照从左到右的顺序遍历，我们维护一个升序的柱子序列，则对于栈顶的柱子，它的左边界就是栈中的前一个柱子，而当我们遍历到某个柱子不符合升序序列，也即比栈顶元素小时，它就是栈顶矩形的右边界。这个时候就可以计算以栈顶为高的矩形的大小了。并且计算后可以将其出栈，这是因为它是目前遍历过的柱子中最高的值，不会对其他矩形产生影响。出栈后，如果这个柱子仍然比新的栈顶小，则仍需要继续这个过程，因此我们使用的是 while 循环。结束过程之后，我们要将这个柱子进栈。
  对于连续两个同样高度的柱子是怎么处理的呢？以它们为高的矩形应该是一样的，因此我们只需要计算其中一个即可。两个都加入栈中的话，右边那个的左边界会被认为是左边这个，因此计算得到的矩形面积会比实际小，左边那个的计算则不会受到影响。我们的结果是要求最大的矩形面积，因此偏小的那个不会对最终结果造成影响。由此可知，我们可以直接将同样高度的也加入到栈中。
  栈中存放的信息是什么？我们需要知道柱子的高度，也即矩形的高；而柱子的宽度是以它的左右边界的下标差来计算的，因此我们也需要知道柱子的下标。因此我们有两种方法，一种是直接存放柱子的下标，每次需要用到柱子高度时再通过柱子下标查询高度；另外一种是直接用一个 pair 将这两个信息存放进去。
  这个题目对于边界是怎么处理的？我们可以利用哨兵的技巧。也即在柱子序列两边添加一个高度为 0 的柱子，这样就可以直接处理边界的柱子了。可是数组不能有下标为 -1 的情况，heights[-1] 是非法的，因此我采用的是 pair 的做法，最开始就在栈中直接添加了一个 {-1, 0}，表示下标为 -1 的柱子高度为 0。这样的好处是栈永远不会为空，并且这个哨兵可以处理其作为左边界的情况。对于右边界的哨兵就更简单了，直接在数组最后添加一个 0 表示一个高度为 0 的柱子即可，这样到最后可以处理掉栈中剩余的所有柱子，只留下两个哨兵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<pair<int, int>> s;
        s.push({-1, 0});
        heights.push_back(0);

        for(int i = 0; i < heights.size(); i++){
            while(heights[i] < s.top().second){
                int height = s.top().second;
                s.pop();
                result = max(result, (i - s.top().first - 1) * height);
            }
            s.push({i, heights[i]});
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是柱子的数量。我们只对数组进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 是柱子的数量。也即栈的开销。