题目描述:

传送门-力扣

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

思路

对于矩阵中位置(i, j)点来说,以该点为右下角点所能包围的最大矩形的面积受到三个方面的影响:

  1. 该坐标向左连续1的个数;
  2. 该坐标向上连续1的个数;
  3. 以及“向上连续1的个数”和“向左连续1的个数”包围的区域中是否有0,详细讨论

对于第 3 点,可以用柱状图来进行计算,有两种方式:

  1. 以该点向左连续的1中,每个1作为起点,分别向上计算连续1的个数,遍历到该列时,取连续1的最小值;
  2. 以该点向上连续的1中,每个1作为起点,分别向左计算连续1的个数,遍历到该行时,取连续1的最小值;

这里选取第2种放法进行计算。

  1. 首先,需要求出矩阵中每一行,连续1的个数,因此将dp[i][j]定义为第i行中,到第j列这个位置连续1的个数。如dp[0][2] = 1,dp[1][4] = 3。知道了每个点的位置在该行中连续1的个数后,就可以计算最大面积了。
  2. 以matrix[i][j]为右下角计算包围的最大矩形,需要从该点向上进行查找每一行中第j列的位置连续1的个数,每遍历一行,就将该行第j列中连续1的数量与记录的最小值比较,取最小值作为矩形的宽度(木桶效应)。
  3. 以向上遍历的行数为矩形的高度,计算出当前矩形面积,并与记录的最大面积比较,取最大的。
  4. 循环第3、4步,直到遍历完第一行(也可以加if判断,当某一行第j列的值为0,就break)。

代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int result = 0;
        if (matrix.empty()) return result;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = dp[i][j - 1] + 1;                //每一行中第j列连续1的个数
                    int minLen = INT_MAX;                       //用于保存小宽度
                    for(int k = 0; k <= i - 1; k++){            //对于该点上面的每一行,进行遍历
                        minLen = min(minLen, dp[i - k][j]);     //取最小宽度(木桶效应)
                        result = max(result, minLen * (k + 1)); //计算面积
                    }
                }
            }
        }
        return result;
    }
};