安徽工建设信息网站,平凉公司网站建设,简单写文章的网站,成都哪里有做网站建设的最大矩形
力扣链接#xff1a;85. 最大矩形
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例 输入#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”…最大矩形
力扣链接85. 最大矩形
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。
示例 输入matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出6 解释最大矩形如上图所示。
Java代码dp
class Solution {public int maximalRectangle(char[][] matrix) {int m matrix.length, n matrix[0].length;int res 0;int[][] dp new int[m1][n1];for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i-1][j-1] 0) continue;dp[i][j] dp[i][j-1] 1;int maxArea dp[i][j], minLength dp[i][j];for (int height 2; i height matrix[i-height][j-1] ! 0; height) {minLength Math.min(minLength, dp[i-height1][j]);maxArea Math.max(maxArea, height * minLength);}res Math.max(res, maxArea);}}return res;}
}其他思路 每一层看作是柱状图可以套用84. 柱状图中最大的矩形的最大面积。
第一层柱状图的高度[“1”,“0”,“1”,“0”,“0”]最大面积为1
第二层柱状图的高度[“2”,“0”,“2”,“1”,“1”]最大面积为3
第三层柱状图的高度[“3”,“1”,“3”,“2”,“2”]最大面积为6
第四层柱状图的高度[“4”,“0”,“0”,“3”,“0”]最大面积为4
这一题的算法本质上和 84.题柱状图中最大的矩形 一样对每一行都求出每个元素对应的高度这个高度就是对应的连续1的长度然后对每一行都更新一次最大矩形面积。那么这个问题就变成了85最大矩形。本质上是对矩阵中的每行均依次执行84题算法。 来源力扣LeetCode 链接https://leetcode.cn/problems/maximal-rectangle 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
