85最大矩形.zip（算法）

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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。