转换-LeetCode85-最大矩形

93 阅读 0 评论 62 点赞

我是靠谱客的博主开朗烤鸡，这篇文章主要介绍转换-LeetCode85-最大矩形，现在分享给大家，希望可以做个参考。

题目

复制代码

1
2
3
4
5
6
7
8
9
10
给定一个仅包含 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数字最小值）。。。取最大矩形面积即为所求。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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;
}
}