84. Largest Rectangle in Histogram.md

84. Largest Rectangle in Histogram

思路

求直方图中面积最大的矩形。

思路一

此题比较好想的思路就是从前往后遍历，求出以heights[i]为高的最大矩形面积，为此我们需要求出此时最大的宽，该怎样求呢？想象一个木桶，总是最低的那块板子决定桶的装水量。所以我们只需要求出heights[i]向左第一个比他小的数heights[j1]和向右第一个比他小的数heights[j2]，宽就为j2 - j1 - 1。

求数组中每个元素的左（右）边第一个比他大（小）的元素可利用单调栈在O(n)时间内求出，关于单调栈可以参考我的总结。

需要至少两次遍历，时间复杂度O(n)；空间复杂度O(n)

思路二

此题还有一个比较难想的思路，也是维护一个单调栈，只需要一次遍历。

我们考虑寻找到所有可能成为最大矩形的右边界（含）heights[i]，这个右边界需要满足一个条件：大于其右边那个元素，即heights[i] > heights[i+1]。例如题目例子中的有三个候选右边界2、6、3。为什么要满足这个条件呢？是因为如果heights[i] <= heights[i+1]，那么包含heights[i]的矩形都可以向右扩展到heights[i+1]，所以heights[i]不可能成为最大矩形右边界，例如题目例子中的i=2时。

因为我们向找到heights[i] > heights[i+1]的情况，所以我么可以维护一个单调递增的栈，栈里面存放的是下标，具体我们这样处理：

• 若heights[i]比栈顶大，直接入栈即可；

• 否则，说明i-1就是我们要找的候选右边界（含），右边界有了那左边界和矩形高呢？我们只能不断往左扩展，为此我们不断出栈直到栈空或者heights[i]比栈顶大：

  • 这个出栈过程中，刚刚出栈的元素对应的height就为矩形的高，此时的栈顶元素设为left就为左边界（不含），所以宽就为i - 1 - left（如果栈空的话宽应该是i），所以此时的候选矩形面积就可以算出来了。（这里比较难理解，需要结合单调递增栈始终满足的条件：栈顶的元素在原数组中的左边第一个比他小的元素就是次顶元素）

  最后将i入栈。

需要注意的是，由于最后一个板子也是候选右边界，所以这里使用一个小技巧：在heights数组最后面push一个0。

只需要遍历一遍，时间复杂度O(n)；空间复杂度O(n)

这个思路还是比较难理解的，需要结合单调递增栈始终满足的特点（栈顶的元素在原数组中的左边第一个比他小的元素就是次顶元素）进行理解。

C++

思路一

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), res = 0;
        
        vector<int>pre_smaller(n), next_smaller(n); // 存的是下标
        stack<int>ascend_stk1, ascend_stk2;
        
        for(int i = 0; i < n; i++){
            while(!ascend_stk1.empty() && heights[ascend_stk1.top()] >= heights[i])
                ascend_stk1.pop();
            pre_smaller[i] = ascend_stk1.empty() ? -1 : ascend_stk1.top();
            ascend_stk1.push(i);
            
            int j = n - i - 1; // 相当于反向遍历: for(int j = n-1; j >= 0; j--)
            while(!ascend_stk2.empty() && heights[ascend_stk2.top()] >= heights[j])
                ascend_stk2.pop();
            next_smaller[j] = ascend_stk2.empty() ? n : ascend_stk2.top();
            ascend_stk2.push(j);
        }

        for(int i = 0; i < n; i++)
            res = max(res, heights[i] * (next_smaller[i] - pre_smaller[i] - 1));
        
        return res;
    }
};

思路二

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        int n = heights.size(), res = 0;
        
        stack<int>ascend_stk;
        for(int i = 0; i < n; i++){
            while(!ascend_stk.empty() && heights[ascend_stk.top()] >= heights[i]){
                int height = heights[ascend_stk.top()]; ascend_stk.pop();
                int width = ascend_stk.empty() ? i : i - 1 - ascend_stk.top();
                res = max(res, height * width);
            }
            ascend_stk.push(i);
        }
        return res;
    }
};