转换-LeetCode85-最大矩形

题目

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

思路

变换为

遍历选取一个点作为长方形左上顶点，计算宽为1的矩形面积（1x该顶点数字）；如果右边有非0数字，再计算宽为2的矩形面积（2x这两个非0数字最小值）；如果右边还有非0数字，再计算宽为3的矩形面积（3x这三个非0数字最小值）。。。取最大矩形面积即为所求。

代码

class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0){
return 0;
}
int res=0;
int[][] nums=new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j]=='1'){
nums[i][j]=1;
}else{
nums[i][j]=0;
}
}
}
//只含0，1的数组转换成不只是包含0，1的统计形式
for(int i=0;i<matrix[0].length;i++){
int sum1=1;
for(int j=matrix.length-1;j>=0;j--){
if(nums[j][i]==1){
nums[j][i]=sum1;
sum1++;
}else{
sum1=1;
}
}
}
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(nums[i][j]!=0){
//连续非0数的个数
int sum2=1;
//连续非0数中最小值
int min=nums[i][j];
if(nums[i][j]>res){
res=nums[i][j];
}
for(int k=j+1;k<matrix[0].length;k++){
if(nums[i][k]!=0){
sum2++;
if(nums[i][k]<min){
min=nums[i][k];
}
int tem_res=sum2*min;
if(tem_res>res){
res=tem_res;
}
}else{
break;
}
}
}
}
}
return res;
}
}

最后

以上就是开朗烤鸡为你收集整理的转换-LeetCode85-最大矩形的全部内容，希望文章能够帮你解决转换-LeetCode85-最大矩形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。