AlgoPressAppearance
0221-最大正方形
https://leetcode.cn/problems/maximal-square
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1： 
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'
基本思路 暴力法
参考代码:暴力法【TODO】
csharp
//暴力法：有问题
public class Solution {
int maxSquare = 0;
public int MaximalSquare(char[][] matrix) {
for(int i=0; i<matrix.Length; i++){
for(int j=0; j<matrix[0].Length; j++){
//计算正方形
int length = Math.Min(matrix.Length-i,matrix[0].Length-j);
for(int ii=i;ii < length; ii++){
for(int jj = j; jj <= ii; jj++){
if(matrix[ii][jj] == 0){
break;
}
}
maxSquare = Math.Max(maxSquare,(length-ii) * (length-ii));
}
}
}
}
}
基本思路2：动态规划【官方解法]
动态规划
dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
注意边界处理，最边界也需要处理为1的面积
csharp
public class Solution {
int maxSquare = 0;
public int MaximalSquare(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
int[,] dp = new int[m,n];
//处理边界
for(int i=0; i<m; i++ ){
dp[i,0] = matrix[i][0] == '1' ? 1 : 0;
maxSquare = Math.Max(maxSquare, dp[i,0] * dp[i,0]);
}
for(int j=0; j<n; j++){
dp[0,j] = matrix[0][j] == '1' ? 1 : 0;
maxSquare = Math.Max(maxSquare, dp[0,j] * dp[0,j]);
}
//动态规划转移
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(matrix[i][j] == '1'){
dp[i,j] = Math.Min(Math.Min(dp[i-1,j],dp[i,j-1]),dp[i-1,j-1]) + 1;
maxSquare = Math.Max(maxSquare, dp[i,j] * dp[i,j]);
}
}
}
return maxSquare;
}
}
复习：20220702
csharp
public class Solution {
public int MaximalSquare(char[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
int[,] dp = new int[m+1,n+1];
int len = 0;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(matrix[i-1][j-1] == '1'){
dp[i,j] = Math.Min(Math.Min(dp[i,j-1],dp[i-1,j]),dp[i-1,j-1])+1;
len = Math.Max(dp[i,j],len);
}
}
}
return len * len;
}
}