问题描述
LeetCode 221. 最大正方形 (opens in a new tab)，难度中等。
在一个由 '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.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为'0'或'1'
题解
DP
解题思路：构建一个 dp 数组，其中 dp[i][j] 的含义是位置 (i, j) 为右下角的最大正方形的边长。
动态转移方程
-
如果
matrix[i][j] == '0'，那么dp[i][j] = 0，因为位置(i, j)不能成为正方形的一部分。 -
如果
matrix[i][j] == '1'，那么dp[i][j]的值取决于其左边、上边和左上角的三个位置的dp值。具体来说，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
Solution.java
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length;
int cols = matrix[0].length;
int maxSide = 0;
int[][] dp = new int[rows][cols];
// 遍历矩阵
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
// dp[i][j] 等于左、上和左上角三个位置的 dp 值的最小值加 1
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
// 更新最大边长
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}