🌕 221. 最大正方形
2022年10月10日
- algorithm
🌕 221. 最大正方形
难度: 🌕
问题描述
解法 1
class Solution {
public int maximalSquare(char[][] matrix) {
// 思路:
// dp[i][j] - 左上角必须是正方形,正上方 & 左方 均是 1
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
// 初始化
int res = 0;
for(int i = 0; i < row; i ++) {
if(matrix[i][0] == '1') {
dp[i][0] = 1;
res = 1;
}
}
for(int j = 0; j < col; j ++) {
if(matrix[0][j] == '1') {
dp[0][j] = 1;
res = 1;
}
}
// dp
for(int i = 1; i < row; i ++) {
for(int j = 1; j < col; j ++) {
if(matrix[i][j] == '1') {
if(dp[i - 1][j - 1] == 0) {
dp[i][j] = 1;
res = Math.max(res, 1);
} else {
// 判断能否形成更大的正方形
int prev = dp[i - 1][j - 1];
int top = i;
while(top >= 0 && top >= i - prev) {
if(matrix[top][j] == '1') {
top --;
} else {
top ++;
break;
}
}
int left = j;
while(left >= 0 && left >= j - prev) {
if(matrix[i][left] == '1') {
left --;
} else {
left ++;
break;
}
}
dp[i][j] = Math.min(prev, Math.min(i - top, j - left)) + 1;
// System.out.println(i + " " + j + " " + dp[i][j]);
res = Math.max(dp[i][j], res);
}
}
}
}
return res * res;
}
}
输出 1
解法 2 - 局部优化
class Solution {
public int maximalSquare(char[][] matrix) {
// 思路:
// dp[i][j] - 左上角必须是正方形,正上方 & 左方 均是 1
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
// 初始化
int res = 0;
for(int i = 0; i < row; i ++) {
if(matrix[i][0] == '1') {
dp[i][0] = 1;
res = 1;
}
}
for(int j = 0; j < col; j ++) {
if(matrix[0][j] == '1') {
dp[0][j] = 1;
res = 1;
}
}
// dp
for(int i = 1; i < row; i ++) {
for(int j = 1; j < col; j ++) {
if(matrix[i][j] == '1') {
if(dp[i - 1][j - 1] == 0) {
dp[i][j] = 1;
res = Math.max(res, 1);
} else {
// 判断能否形成更大的正方形
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
// System.out.println(i + " " + j + " " + dp[i][j]);
res = Math.max(dp[i][j], res);
}
}
}
}
return res * res;
}
}