# [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

# 思路

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

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

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

需要至少两次遍历，时间复杂度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++
## 思路一
``` 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;
    }
};
```

## 思路二
``` C++
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;
    }
};
```