mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
89 lines
4.3 KiB
Markdown
89 lines
4.3 KiB
Markdown
# [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;
|
||
}
|
||
};
|
||
```
|