最大正方形：用相邻状态确定边长

核心结论#

令 dp[row][column] 表示以当前单元格为右下角、只包含 1 的最大正方形边长。当当前值为 1 时，它由左、上、左上三个状态的最小值加一决定。

状态定义#

如果三个相邻方向中任意一个只能形成较小正方形，当前正方形就不能越过它。因此转移方程为：

dp[row][column] = min(
  dp[row - 1][column],
  dp[row][column - 1],
  dp[row - 1][column - 1]
) + 1

第一行和第一列没有完整的三个前置状态，可以通过额外增加一圈全零边界来统一处理。

Java 实现#

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int[][] dp = new int[rows + 1][columns + 1];
        int maxSide = 0;

        for (int row = 1; row <= rows; row++) {
            for (int column = 1; column <= columns; column++) {
                if (matrix[row - 1][column - 1] == '1') {
                    dp[row][column] = Math.min(
                        Math.min(dp[row - 1][column], dp[row][column - 1]),
                        dp[row - 1][column - 1]
                    ) + 1;
                    maxSide = Math.max(maxSide, dp[row][column]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

正确性与复杂度#

状态只在当前格为 1 时扩展，且三个相邻正方形共同保证新扩展的一行和一列均为 1。遍历完成后，最大边长的平方就是所求面积。

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)，可用滚动数组进一步降到 O(n)。

验证#

测试空矩阵、全为 0、单个 1、非正方形矩阵，以及最大正方形贴近边界的情况。

参考#

• LeetCode 221：最大正方形