潜江公司做网站,毕节网站网站建设,深圳专业网站建设公司多少钱,凡科网站免费版怎么做85. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵#xff0c;找出只包含 1 的最大矩形#xff0c;并返回其面积。
示例 1#xff1a; 输入#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”…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
示例 3
输入matrix [[“0”]] 输出0
示例 4
输入matrix [[“1”]] 输出1
示例 5
输入matrix [[“0”,“0”]] 输出0
提示
rows matrix.lengthcols matrix[0].length0 row, cols 200matrix[i][j] 为 ‘0’ 或 ‘1’
解题思路
利用84. 柱状图中最大的矩形的代码我们只需要将连续的1计算为高度就和那题没什么区别了
代码
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix.length0) return 0;int[] hnew int[matrix[0].length];int res0;for(int i0;imatrix.length;i){for(int j0;jmatrix[0].length;j){if(matrix[i][j]0){h[j]0;}else h[j];}resMath.max(res,largestRectangleArea(h));}return res;}public int largestRectangleArea(int[] heights) {StackInteger stacknew Stack();int nheights.length;int[] nhnew int[n2];for(int i0;in;i)nh[i1]heights[i];int res0;for(int i0;in2;i){while(!stack.isEmpty()nh[i]nh[stack.peek()]){int jstack.pop(),hnh[j];int wi-stack.peek()-1;resMath.max(res,h*w);}stack.push(i);}return res;}
}
