Maximal Rectangle

1,题目要求

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

Example:
Input:

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

Output: 6

给定填充0和1的2D二进制矩阵,找到仅包含1的最大矩形并返回其区域。

2,题目思路

对于这道题,计算一个矩阵内的最大的矩形面积。

在解决这个问题上,我们使用动态规划的思路来实现。
对于矩形的每个点(row, col), 我们计算:

  • 改点上方的连续的‘1’往left、right方向延伸所能达到的最大的矩形的面积。
  • **left:**向左可以延伸到的最左的位置
  • **right:**向右可以延伸到的最右的位置+1

因为我们始终要保持一个矩形,因此,为了防止出现“”的情况,因此:

  • 最左侧的坐标,我们取max
  • 最右侧的坐标,我们取min

在遍历时,从上往下增加行数,每增加一行,根据当前节点是否是1,来对矩形的高度进行更新(height[j]++ 或者 height[j] = 0),然后,把当前行往上所有能够构成矩形的面积计算出来,这个面积的宽度取决于最大的满足矩形条件的连续的1的个数(right[j] - left[j]),高度则就是height[j],然后再与最大值比较,记录最大值。
遍历到最后一行时,就找到最终结果了。

3,代码实现

1,带有注释、便于理解

static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
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> left (n, 0);
        vector<int> right (n, n);
        vector<int> height (n, 0);
        
        int maxArea = 0;
        for(int i = 0;i<m;i++){
            int curLeft = 0, curRight = n;
            //计算当前节点对应的最大高度
            for(int j = 0;j<n;j++){ 
                if(matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            //计算当前节点向左所能达到的可行的最远位置,默认为0,即达到最左
            for(int j = 0;j<n;j++){
                if(matrix[i][j] == '1')
                    left[j] = max(left[j], curLeft);    //取前几行的最远索引位置和当前最远索引位置的最大值,即最靠近当前节点的左侧位置,以保证不会出现'凸'的情况
                else{
                    left[j] = 0;   //恢复为初值,反正当前点也一定不会再可行矩形内
                    curLeft = j+1;
                }
            }
            //计算当前节点向右所能达到的可行的最远位置,默认为n,即达到最右
            for(int j = n-1;j>=0;j--){
                if(matrix[i][j] == '1')
                    right[j] = min(right[j], curRight); //同理,此时是利用去min,同样保证不会出现'凸'的情况
                else{
                    right[j] = n;
                    curRight = j;
                }
            }
            //计算此时最大的矩形面积
            for(int j = 0;j<n;j++)
                maxArea = max(maxArea, (right[j] - left[j])*height[j]);
        }
        return maxArea;
    }
};

2,原理相同,简化代码

class Solution {
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> left(n, 0), right(n, n), height(n, 0);
        int maxArea = 0;
        for(int i = 0;i<m;i++){
            int curLeft = 0, curRight = n;
            for(int j = n-1;j>=0;j--)
                if(matrix[i][j] == '1') right[j] = min(right[j], curRight);
                else{ right[j] = n, curRight = j;}
            for(int j = 0;j<n;j++){
                if(matrix[i][j] == '1'){
                    height[j]++;
                    left[j] = max(left[j], curLeft);
                }
                else{
                    height[j] = 0;
                    left[j] = 0, curLeft = j+1;
                }
                maxArea = max(maxArea, (right[j] - left[j])*height[j]);
            }
        }
        return maxArea;
    }
};
上一篇:poj 2411 Mondriaan's Dream (状压dp)


下一篇:【HDU6514】Monitor(二维树状数组)