85. 最大矩形
困难
相关标签
相关企业
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = [["0"]]
输出：0
示例 3：
输入：matrix = [["1"]]
输出：1
提示：
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if (m == 0) {
return 0;
}
int n = matrix[0].length;
int[][] left = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
continue;
}
int width = left[i][j];
int area = width;
for (int k = i - 1; k >= 0; k--) {
width = Math.min(width, left[k][j]);
area = Math.max(area, (i - k + 1) * width);
}
ret = Math.max(ret, area);
}
}
return ret;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/maximal-rectangle/solutions/535672/zui-da-ju-xing-by-leetcode-solution-bjlu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
