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

发表于 更新于

原本并没有重视这个技巧，但是后来回过头再来做几道关于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
24
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
36
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;
    }
};