题目链接：Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

这道题的要求是在0-1矩阵中找出面积最大的全1矩阵。

  1. 基于Largest Rectangle in Histogram

假设把矩阵沿着某一行分开，然后把分开的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。

如何计算某一行为底面时直方图的高度呢？如果重新计算，那么每次需要的计算数量就是当前行数乘以列数。然而会发现一些动态规划的踪迹，如果知道上一行直方图的高度，就只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。利用历史信息，就可以在线行时间内完成对高度的更新。由于Largest Rectangle in Histogram的算法复杂度是O(n)。所以完成对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次，那么算法总时间复杂度是O(m*n)。

时间复杂度：O(mn)

空间复杂度：O(n)

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
37
38
39

class Solution
{
public:
    int maximalRectangle(vector<vector<char> > &matrix)
    {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        
        int res = 0;
        vector<int> height(matrix[0].size(), 0);
        for(int i = 0; i < matrix.size(); ++ i)
        {
            for(int j = 0; j < matrix[0].size(); ++ j)
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            res = max(res, largestRectangleArea(height));
        }
        return res;
    }
private:
    int largestRectangleArea(vector<int> &height)
    {
        int res = 0;
        stack<int> si;
        height.push_back(0);
        for(int i = 0; i < height.size(); ++ i)
        {
            while(!si.empty() && height[si.top()] >= height[i])
            {
                int h = height[si.top()];
                si.pop();
                
                int s = h * (si.empty() ? i : (i - si.top() - 1));
                res = max(res, s);
            }
            si.push(i);
        }
        return res;
    }
};

  1. 动态规划

思路同样是从第一行开始一行一行地处理，使[i, j]处最大子矩阵的面积是(right(i, j)-left(i, j))*height(i, j)。其中height统计当前位置及往上’1’的数量；left和right是高度是当前点的height值得左右边界，即是以当前点为中心，以height为高度向两边扩散的左右边界。

递推公式如下：

left(i, j) = max(left(i-1, j), cur_left);
right(i, j) = min(right(i-1, j), cur_right);
height(i, j) = height(i-1, j) + 1, if matrix[i][j]=='1';
height(i, j) = 0, if matrix[i][j]=='0'.

其中cur_left和cur_right的值由当前行决定，如果当前位置是’1’，则cur_left和cur_right都不变；如果当前位置是’0’，则cur_left就为当前位置的右侧，cur_right就为当前位置（因为左闭右开）。

详见这里。

时间复杂度：O(mn)

空间复杂度：O(n)

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
37

class Solution
{
public:
    int maximalRectangle(vector<vector<char> > &matrix)
    {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<int> left(n, 0), right(n, n), height(n, 0);
        
        for(int i = 0; i < m; ++ i)
        {
            int cur_left = 0, cur_right = n;
            
            for(int j = 0; j < n; ++ j)
                height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
            
            for(int j = 0; j < n; ++ j)
            {
                left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0;
                cur_left = matrix[i][j] == '1' ? cur_left : j + 1;
            }
            
            for(int j = n - 1; j >= 0; -- j)
            {
                right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
                cur_right = matrix[i][j] == '1' ? cur_right : j;
            }
            
            for(int j = 0; j < n; ++ j)
                res = max(res, (right[j] - left[j]) * height[j]);
        }
        
        return res;
    }
};