直方图的最大矩形面积的栈优化思想

原本并没有重视这个技巧,但是后来回过头再来做几道关于DP的题目,意外地发现这个做法可以将O(n^2)的复杂度优化至O(n)!所以打算将这类题目做一个总结吧。


直方图最大矩形覆盖

Description

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.

For example, given height = [2,1,5,6,2,3].

heights

The largest rectangle area is 10 unit.

area

Thinking

基本思想:用栈维护一个递增子序列

为了方便记录矩形的宽度,我们在栈中存放的是矩形的下标。

我们用 i 遍历所有的矩形,当栈尾元素 j 对应的矩形高度大于或等于当前遍历到的矩形时(出现了局部非递增),可以保证:前面出现的上升序列中可能存在最大面积。如下图:

这样当遇到局部递减时,依次取出栈尾,如果 s 未空面积 area = height[cur] * (i-s.top()-1) 就是栈尾元素对应的高度乘以跨度,如果此时s已空, area = height[cur] * i

最后需要注意,为防止全是单调上升的情况导致 s 无法清空,可以增设一个高度为 0 的矩形。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
int result = 0;
height.push_back(0);
stack<int> s;
for (int i = 0; i < height.size(); ++i) {
while (!s.empty() && height[s.top()] >= height[i]) {
int cur = s.top(), area;
s.pop();
if (s.empty()) area = height[cur] * i;
else area = height[cur] * (i-s.top()-1);
result = max(result, area);
}
s.push(i);
}
return result;
}
};

最大矩形

Description

给你一个二维矩阵,权值为False和True,找到一个最大的矩形,使得里面的值全部为True,输出它的面积

比如,给你一个矩阵如下

1
2
3
4
5
1  1  0  0  1
0 1 0 0 1
0 0 1 1 1
0 0 1 1 1
0 0 0 0 1

答案是6

Thinking

先用类似前缀和的做法先预处理原矩形,在纵向上来看,所有的1可以类加成高度

1
2
3
4
5
1  1  0  0  1
0 2 0 0 2
0 0 1 1 3
0 0 2 2 4
0 0 0 0 5

于是可以在O(1)的时间里获得当前行的矩形高度,然后用类似“直方图最大矩形面积”的做法求出每一行段的最大面积,就可以找出最大值。

综上,时间复杂度O(n^2)

Code

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
28
29
30
31
32
33
34
35
class Solution {
private:
int getLayerMax(vector<int> &height) {
int _max = 0, size = height.size();
stack<int> s;
height.push_back(0);
for (int i = 0; i < height.size(); ++i) {
while (!s.empty() && height[i] <= height[s.top()]) {
int cur = s.top();
s.pop();
if (s.empty()) _max = max(_max, height[cur]*i);
else _max = max(_max, height[cur]*(i-s.top()-1));
}
s.push(i);
}
return _max;
}
public:
int maximalRectangle(vector<vector<bool> > &matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), _max = 0;

vector<vector<int> > prefix(m, vector<int>(n, 0));

for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
if (!matrix[i][j]) prefix[i][j] = 0;
else prefix[i][j] = (i==0) ? 1 : prefix[i-1][j] + 1;

for (int i = 0; i < m; ++i)
_max = max(_max, getLayerMax(prefix[i]));

return _max;
}
};