221. 最大正方形
解题思路
- 参考题解:
https://leetcode.cn/problems/maximal-square/solutions/44586/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/?show=1
- 主要思想:选择左边 上面 左上方 最小的值,dp[i+1][j+1]代表以第i行 第j列为右下角的正方形的最大边长
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
return 0;
}
int height = matrix.length;
int width = matrix[0].length;
int maxSide = 0;
int[][] dp = new int[height + 1][width + 1];
for(int row = 0; row < height; row++){
for(int col = 0; col < width; col++){
if(matrix[row][col] == '1'){
dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col],dp[row][col+1]),dp[row][col]) + 1;
maxSide = Math.max(maxSide,dp[row+1][col+1]);
}
}
}
return maxSide * maxSide;
}
}