当前位置 博文首页 > 数据结构和算法：LeetCode 221. 最大正方形
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
有可能是下面这种情况，就是左边或者上边的某一个高度小于dp[i-1][j-1]的值，要想构成最大的正方形我们只能取最小的。
也有可能是下面这种，就是左边和上边的高度都不小于dp[i-1][j-1]的值。
public int maximalSquare(char[][] matrix) {
//二维矩阵的宽和高
int height = matrix.length;
int width = matrix[0].length;
int[][] dp = new int[height + 1][width + 1];
int maxSide = 0;//最大正方形的宽
for (int i = 1; i <= height; i++) {
for (int j = 1; j <= width; j++) {
if (matrix[i - 1][j - 1] == '1') {
//递推公式
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
//记录最大的边长
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
//返回正方形的面积
return maxSide * maxSide;
}
