LeetCode 第 221 题：最大正方形（中等）
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例：
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：动态规划
注意：状态多一个单位的偏移，这样不用讨论特殊情况。
Java 代码：
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if (rows == 0) {
return 0;
}
int cols = matrix[0].length;
if (cols == 0) {
return 0;
}
int[][] dp = new int[rows + 1][cols + 1];
int res = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 注意：是字符 1
if (matrix[i][j] == '1') {
dp[i + 1][j + 1] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
res = Math.max(res, dp[i + 1][j + 1]);
}
}
}
return res * res;
}
}
方法二：动态规划（注意状态压缩的技巧）
Java 代码：
public class Solution {
// 状态多一个单位的偏移，这样不用讨论特殊情况
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if (rows == 0) {
return 0;
}
int cols = matrix[0].length;
if (cols == 0) {
return 0;
}
int[] dp = new int[cols + 1];
int res = 0;
int leftUp = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 把下一个需要的状态值保存起来
int nextLeftUp = dp[j + 1];
// 注意：是字符 1
if (matrix[i][j] == '1') {
dp[j + 1] = Math.min(leftUp, Math.min(dp[j], dp[j + 1])) + 1;
res = Math.max(res, dp[j + 1]);
} else {
// 注意：这里要重置一下
dp[j + 1] = 0;
}
leftUp = nextLeftUp;
}
}
return res * res;
}
}