[leetcode] 85. Maximal Rectangle-蒲公英云

[leetcode] 85. Maximal Rectangle

85. Maximal Rectangle
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
return 6.

给定一个二维矩阵，里面的元素分别为1或者0，找出一个矩阵，元素都是1，并返回该矩阵的面积。
例如，给定矩阵如下：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
则返回矩阵的面积为6。

解题思路
这道题的难度系数标记为Hard。因为我们要找的是一个全是1的二维矩阵，也就是说该矩阵是以某个元素开始，然后以该元素有起点分别向右和向下延伸，形成一个矩阵。
本题可通过动态规划进行求解。

代码实现如下：

class Solution {
// 时间复杂度 O(n^2)，空间复杂度 O(n)
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        const int m = matrix.size();
        const int n = matrix[0].size();
        vector<int> H(n, 0);
        vector<int> L(n, 0);
        vector<int> R(n, n);
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            int left = 0, right = n;
        //calculate L(i,j) from left to right
            for(int j = 0; j < n; ++j)
            {
                if(matrix[i][j] == '1')
                {
                    ++H[j];
                    L[j] = max(L[j], left);
                }
                else
                {
                    left = j+1;
                    H[j] = 0;
                    L[j] = 0;
                    R[j] = n;
                }
            }
            //calculate R(i,j) from right to left
            for(int j = n-1; j >= 0; --j)
            {
                if(matrix[i][j] == '1')
                {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j]*(R[j] - L[j]));
                }
                else
                {
                    right = j;
                }
            }
        }
        return ret;
    }
};