221. 最大正方形

动态规划解法

🧠 解题思路（动态规划）

我们定义 dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。

• 如果 matrix[i][j] == '0'，那么 dp[i][j] = 0，因为无法构成全为 '1' 的正方形。

• 如果 matrix[i][j] == '1'，则：

  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  

因为要形成一个更大的正方形，左、上、左上三个方向都必须能构成正方形，取其中最小的边长，再加 1。

最后记录所有 dp[i][j] 中的最大值 maxSide，面积就是 maxSide * maxSide。

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[][] dp = new int[rows][cols];

        int maxSide = 0;
        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] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    }
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
        return maxSide * maxSide;
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(m × n)，遍历整个矩阵一次。
• 空间复杂度：O(m × n)，使用了二维 dp 数组。

优化存储空间

🧠 优化思路

原始状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

如果我们用一维数组 dp[j] 表示当前行第 j 列的最大边长，那么：

• dp[j] 在更新前保存的是 上一行 的值（即 dp[i-1][j]）
• dp[j-1] 是当前行已经更新过的值（即 dp[i][j-1]）
• 但 dp[i-1][j-1]（左上角）在更新 dp[j] 时已经被覆盖了！

👉 所以我们需要一个变量 prev 来临时保存 dp[i-1][j-1]。

具体做法：

• 遍历每一行时，从左到右更新 dp[j]
• 用 temp 保存更新前的 dp[j]（即下一轮的 prev）
• 更新 dp[j] 时，prev 就是左上角的值

🔍 关键点说明

• 必须显式设置 dp[j] = 0 当 matrix[i][j] == '0'，否则会残留上一行的值，导致错误。
• prev 的作用是保存“左上角”（dp[i-1][j-1]）的值，在 dp[j] 被覆盖前记录下来。
• 初始化时 dp 数组全为 0，符合边界条件。

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[] dp = new int[cols];
        int maxSide = 0;

        for (int i = 0; i < rows; i++) {
            int prev = 0; // 用于保存 dp[i-1][j-1]
            for (int j = 0; j < cols; j++) {
                int temp = dp[j]; // 保存当前 dp[j]（即将变成 prev）
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[j] = 1;
                    } else {
                        dp[j] = Math.min(prev, Math.min(dp[j], dp[j - 1])) + 1;
                    }
                }else{
                    dp[j] = 0;
                }
                prev = temp;
                maxSide = Math.max(maxSide, dp[j]);
            }
        }
        return maxSide * maxSide;
    }
}

⏱️ 复杂度

• 时间复杂度：O(m × n)
• 空间复杂度：O(n)

如果矩阵列数远小于行数，也可以按列滚动，进一步优化为 O(min(m, n))，但通常 O(n) 已足够高效。

存储O(1)实现

原地修改输入矩阵，将 char[][] matrix 本身当作 DP 数组使用。

⚠️ 注意：这种方法会修改原始输入数据。在实际工程中，如果输入不可变（immutable），则不推荐；但在 LeetCode 这类题目中是允许的，且能达成 O(1) 空间复杂度。

🧠 核心思想

我们将 matrix[i][j] 从字符 '0'/'1' 转换为整数边长（以字符形式存储），表示以 (i, j) 为右下角的最大正方形边长。

• 原始值：'0' 或 '1'
• 更新后：若为 '1'，则替换为 '2', '3', ... 表示边长（仍用 char 存储数字字符）

状态转移方程不变：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

但所有操作都在 matrix 上进行。

🔍 关键细节说明

1. 边界处理：

   • 第一行和第一列无法构成大于 1 的正方形，所以它们的值只能是 '0' 或 '1'。
   • 我们只需检查是否存在 '1'，若有，则 maxSide 至少为 1。

2. 字符与整数转换：

   • matrix[i][j] - '0' 将字符 '2' 转为整数 2
   • (char)('0' + value) 将整数转回字符

3. 不破坏逻辑：

   • 因为我们是从左到右、从上到下遍历，访问 matrix[i-1][j]、matrix[i][j-1]、matrix[i-1][j-1] 时，它们已经被正确更新为“边长字符”，可以直接用于计算。

4. '0' 不处理：

   • 若 matrix[i][j] == '0'，跳过，保持原样，不影响后续计算。

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;

        // 第一行和第一列：直接更新为数字字符，并记录最大值
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == '1') {
                maxSide = 1;
            }
        }
        for (int i = 1; i < rows; i++) {
            if (matrix[i][0] == '1') {
                maxSide = 1;
            }
        }

        // 从 (1,1) 开始遍历
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    // 取左、上、左上三个方向的最小边长（注意转成 int）
                    int left = matrix[i][j - 1] - '0';
                    int top = matrix[i - 1][j] - '0';
                    int topLeft = matrix[i - 1][j - 1] - '0';
                    int min = Math.min(Math.min(left, top), topLeft);
                    matrix[i][j] = (char) ('0' + min + 1); // 存回字符
                    maxSide = Math.max(maxSide, min + 1);
                }
                // 如果是 '0'，保持不变（不影响后续）
            }
        }

        return maxSide * maxSide;
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(m × n)
• 空间复杂度：O(1) 额外空间（仅用几个变量，输入矩阵被复用）

💡 总结