在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
本题直观上来说可以用暴力枚举,每次遍历到一个1,就扫描看看以它形成的正方形最大能多大既可。
但是注意由于我们遍历是从左到右,从上到下,因此每次形成的正方形也只要往这个方向遍历既可,因为如果需要往左往上遍历成一个正方形,那之前就一定已经遍历过了。所以不需要再往那个方向遍历了。
代码如下:
public class Solution {
public int maximalSquare(char[][] matrix) {
int row = matrix.length;
if(row == 0) return 0;
int column = matrix[0].length;
int maxlen = 0;
for(int i = 0; i < row ;i++ ){
for(int j = 0;j < column;j++ ){
if(matrix[i][j] == '1'){
boolean flag = true;
int squareLength = 1;
while(squareLength + i < row && squareLength + j < column && flag){
for(int k = i; k <= squareLength + i; k++ ){
if(matrix[k][squareLength+j] == '0'){
flag = false;
break;
}
}
for(int k = j; k <= squareLength + j; k++ ){
if(matrix[squareLength+i][k] == '0'){
flag = false;
break;
}
}
if(flag)
squareLength++;
}
if(squareLength> maxlen){
maxlen = squareLength;
break;
}
}
}
}
return maxlen*maxlen;
}
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
网友评论