01矩阵找最大正方形面积

这道题是经典的动态规划问题。

一、算法思路

设二维 01 数组为 matrix，定义：

dp[i][j] 表示以 (i,j) 作为右下角时，能够形成的最大正方形边长。

如果当前位置 matrix[i][j] == 0，那么显然：

dp[i][j] = 0

如果当前位置是 1，那么要形成一个以它为右下角的正方形，需要同时保证：

• 上方 (i-1,j) 能形成正方形
• 左方 (i,j-1) 能形成正方形
• 左上方 (i-1,j-1) 能形成正方形

因此：

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

为什么取 min？

假设三个方向分别能形成边长 3、2、3 的正方形，那么当前点最多只能把它们拼成边长 3 的正方形；但因为左边只有 2，实际上当前点只能形成边长 3？这里要注意：当前点作为右下角时，三个方向都至少需要覆盖 k-1 的范围，所以最终边长只能是三个方向中的最小值 +1。例如三个值为 3、2、3，结果就是 3。

遍历过程中维护最大的边长 maxSide，最后面积就是：

maxSide * maxSide

时间复杂度为 O(mn)，空间复杂度可以优化到 O(n)。

---

二维 DP 版本

C++：

#include <bits/stdc++.h>
using namespace std;

int maximalSquare(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();

    vector<vector<int>> dp(m, vector<int>(n, 0));
    int maxSide = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = min({
                        dp[i - 1][j],
                        dp[i][j - 1],
                        dp[i - 1][j - 1]
                    }) + 1;
                }

                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

JavaScript：

function maximalSquare(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;

    const dp = Array.from(
        { length: m },
        () => Array(n).fill(0)
    );

    let maxSide = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; 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],
                            dp[i][j - 1],
                            dp[i - 1][j - 1]
                        ) + 1;
                }

                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

空间优化

实际上 dp[i][j] 只依赖于：

上一行的 dp[i-1][j]
当前行左边的 dp[i][j-1]
左上角的 dp[i-1][j-1]

所以不需要保存整个二维数组，只需要一个一维数组。

这里有一个实现细节：更新 dp[j] 之前，它还是上一行的值；因此用变量 prev 保存左上角的旧值。

C++：

int maximalSquare(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();

    vector<int> dp(n, 0);

    int maxSide = 0;
    int prev = 0;

    for (int i = 0; i < m; ++i) {
        prev = 0;

        for (int j = 0; j < n; ++j) {
            int temp = dp[j];  // 保存更新前的 dp[j]，即左上角

            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[j] = 1;
                } else {
                    dp[j] = min({
                        dp[j],       // 上
                        dp[j - 1],   // 左
                        prev         // 左上
                    }) + 1;
                }

                maxSide = max(maxSide, dp[j]);
            } else {
                dp[j] = 0;
            }

            prev = temp;
        }
    }

    return maxSide * maxSide;
}

JavaScript：

function maximalSquare(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;

    const dp = Array(n).fill(0);

    let maxSide = 0;
    let prev = 0;

    for (let i = 0; i < m; i++) {
        prev = 0;

        for (let j = 0; j < n; j++) {
            const temp = dp[j]; // 更新前的 dp[j]，即左上角

            if (matrix[i][j] === 1) {
                if (i === 0 || j === 0) {
                    dp[j] = 1;
                } else {
                    dp[j] =
                        Math.min(
                            dp[j],     // 上
                            dp[j - 1], // 左
                            prev       // 左上
                        ) + 1;
                }

                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0;
            }

            prev = temp;
        }
    }

    return maxSide * maxSide;
}