题目描述:
给定一个仅包含 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的个数;
- 以及“向上连续1的个数”和“向左连续1的个数”包围的区域中是否有0,详细讨论
对于第 3 点,可以用柱状图来进行计算,有两种方式:
- 以该点向左连续的1中,每个1作为起点,分别向上计算连续1的个数,遍历到该列时,取连续1的最小值;
- 以该点向上连续的1中,每个1作为起点,分别向左计算连续1的个数,遍历到该行时,取连续1的最小值;
这里选取第2种放法进行计算。
- 首先,需要求出矩阵中每一行,连续1的个数,因此将dp[i][j]定义为第i行中,到第j列这个位置连续1的个数。如dp[0][2] = 1,dp[1][4] = 3。知道了每个点的位置在该行中连续1的个数后,就可以计算最大面积了。
- 以matrix[i][j]为右下角计算包围的最大矩形,需要从该点向上进行查找每一行中第j列的位置连续1的个数,每遍历一行,就将该行第j列中连续1的数量与记录的最小值比较,取最小值作为矩形的宽度(木桶效应)。
- 以向上遍历的行数为矩形的高度,计算出当前矩形面积,并与记录的最大面积比较,取最大的。
- 循环第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; } };