LeetCode84 Largest Rectangle in Histogram

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

样例

1
2
3
4
5
Input:
[2,1,5,6,2,3]

Output:
10

思路

在直方图中找到面积最大的矩形。

暴力的做法是,枚举每个点$h[i]$作为最小值,看它能向左扩展多远$l_i$,能向右扩展多远$r_i$, $ans = max \lbrace h[i] * (l_i + r_i) | i = 0..n-1 \rbrace $,复杂度$O(n^2)$。

这题其实是一道单调栈的经典题,使用单调栈可以快速维护出每个点的$l$和$r$值。单调栈中存放节点的信息,表示节点的高度$h_i$以及节点的$l_i$值,并通过$l_i$值推出相应的$r_i$值。单调栈按节点的高度递增排序。

接下来以样例为例,具体说明各个步骤。(红色代表进栈,蓝色代表出栈)

一开始栈为空,第一个节点 $Node_1:\lbrace h = 2, l = 1 \rbrace$ 进栈。

由于当前节点 $Node_2:\lbrace h = 1, l = 1 \rbrace$ 与栈顶节点 $Node_1:\lbrace h = 2, l = 1 \rbrace$ 之间不满足单调性质,故栈顶元素出栈,计算蓝色部分的面积,并更新答案 , $area_1 = h_1 * (l_1 + r_1) = 2 * (1 + 0) = 2$, $ans = max(ans, area_1) = 2$。

此时栈为空,接下来节点 $Node_2:\lbrace h = 1, l = 2 \rbrace$ 进栈,那么我们如何知道该节点向左延伸的最长距离为$2$呢?
前面提到,栈中的节点按高度递增排序,如果当前节点进栈之前,有若干节点由于破坏单调性而被弹出栈,则这些出栈的节点的高度一定是大于当前节点的高度的,也就说明当前节点可以往前延伸这么多的距离。
$Node_2$初始$l_2$值为$1$,由于$Node_1$被弹出栈,那么$Node_2$向左延伸的距离除了本身的$1$以外,还要加上$Node_1$延伸的长度$l_1$。因此$l_2 = 1 + l_1 = 1 + 1 = 2$。

节点 $Node_3:\lbrace h = 5, l = 1 \rbrace$ 正常进栈。

节点 $Node_4:\lbrace h = 6, l = 1 \rbrace$ 正常进栈。

节点 $Node_5:\lbrace h = 2, l = 1 \rbrace$ 想要进栈,但是发现栈顶元素破坏单调性,则节点$Node_4:\lbrace h = 6, l = 1 \rbrace$出栈,更新答案,$area_4 = h_4 * (l_4 + r_4) = 6 * (1 + 0) = 6$, $ans = max(ans, area_4) = 6$。

此时,栈顶为节点 $Node_3:\lbrace h = 5, l = 1 \rbrace$,依旧破坏单调性,出栈,更新答案。
但是$Node_3$进栈时的$l_3$值为$1$,为什么图中蓝色的宽度为$2$呢?请不要忘记计算节点的$r$值!(由于前几个节点的$r$值都为$0$,我就忽略没讲$r$ 怎么算)
那么$r$值又是怎么算出来的呢?这就体现了单调栈的作用了!由于单调栈中节点的高度是递增排列的,因此如果节点$Node_3$出栈前有若干节点被弹出栈了的话,那么这些节点的高度一定是大于节点$Node_3$的,只要把这些节点的$l$值累加起来,就是$Node_3$的$r$值了!因此$r_3 = l\ _4 = 1$。$area_3 = h_3 * (l_3 + r_3) = 5 * (1 + 1) = 10$。$ans = max(ans, area_3) = 10$。

节点 $Node_5:\lbrace h = 2, l = 3 \rbrace$进栈,其中$l_5 = 1 + l_3 + l_4 = 1 + 1 + 1 = 3$。

节点 $Node_6:\lbrace h = 3, l = 1 \rbrace$ 正常进栈。

至此,所有节点都已进栈,其中节点$Node_1$、节点$Node_3$和节点$Node_4$都已经被弹出栈,出栈时也更新过答案了。
现在栈中还有节点$Node_2$、节点$Node_5$和节点$Node_6$。
节点$Node_6:\lbrace h = 3, l = 1 \rbrace$出栈,更新答案,$area_6 = h_6 * (l_6 + r_6) = 3 * (1 + 0) = 3$, $ans = max(ans, area_6) = 10$。

节点$Node_5:\lbrace h = 2, l = 3 \rbrace$出栈,更新答案。其中$r_5 = l_6 = 1$,$area_5 = h_5 * (l_5 + r_5) = 2 * (3 + 1) = 8$, $ans = max(ans, area_5) = 10$。

节点$Node_2:\lbrace h = 1, l = 2 \rbrace$出栈,更新答案。其中$r_2 = l_5 +l_6 = 3 + 1 = 4$,$area_2 = h_2 * (l_2 + r_2) = 1 * (2 + 4) = 6$, $ans = max(ans, area_2) = 10$。

注意到,上述过程中每个节点只进栈和出栈各一次,因此复杂度是线性的!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
struct Node {
int h; // 节点i的高度
int l; // 节点i向左延伸的最长距离
Node(){}
Node(int height, int cnt):h(height), l(cnt){}
};
int largestRectangleArea(vector<int>& heights) {
stack<Node> sta;
int ans = 0, curl;
for (int& h: heights) {
curl = 0;
while (!sta.empty() && sta.top().h >= h) {
ans = max(ans, (curl += sta.top().l) * sta.top().h);
sta.pop();
}
sta.push(Node(h, curl + 1));
}
curl = 0;
while (!sta.empty()) {
ans = max(ans, (curl += sta.top().l) * sta.top().h);
sta.pop();
}
return ans;
}
};
分享到 评论