最大正方形 图解题解

最大正方形这道题在问什么

给一个只含 0 和 1 的矩阵，找出其中面积最大、内部全是 1 的正方形，返回它的面积。两个容易看漏的点：一是要的是正方形不是矩形，长宽必须相等；二是题目问的是面积，算出最大边长后别忘了平方再返回。

为什么暴力枚举正方形太慢

直觉做法是枚举每个格子当正方形的一个角，再枚举每种边长，逐格检查内部是否全 1。m×n 的矩阵有 m·n 个起点、每个起点最多 min(m,n) 种边长、每次检查又要看边长平方个格子，几层循环叠上去开销很大，而且大量检查在重复劳动——边长 3 的正方形内部那些格子，早在检查边长 2 时就看过一遍了。

重复劳动提示了突破口：一个大正方形成不成立，其实不必逐格重查，它可以由「旁边更小的正方形成不成立」直接推出来。能用小结论拼大结论，就是动态规划的信号。

dp 为什么定义成「以这格为右下角的最大边长」

定义 dp[i][j] 为：以格子 (i,j) 作为右下角、内部全 1 的正方形的最大边长。选「右下角」做锚点是因为每个正方形都有且只有一个右下角——按右下角分类枚举，所有正方形不重不漏；而值存边长而非面积，是为了让相邻格子的结论能直接做算术比较。原图为 0 的格子当不了任何全 1 正方形的右下角，dp 直接记 0。

整张 dp 表填完后，全局最大的 dp 值就是最大边长，平方即答案。

为什么取上左左上三者的最小值加一

想以 (i,j) 为右下角撑起一个边长 k 的正方形，等价于三件事同时成立：它上边那格能撑住边长 k-1 的正方形（覆盖上方区域）、左边那格能撑住 k-1（覆盖左侧区域）、左上那格也能撑住 k-1（覆盖左上对角区域），三块拼起来恰好铺满除当前格外的整个 k×k 区域。三个方向里任何一个短了，大正方形就在那个方向缺角，所以能扩到的边长由短板决定——取三者最小值，再加 1 把当前这格接进来，就是转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

只看上、左两个邻居为什么不行？因为它们都撑得住时，左上方向可能有空洞——上邻居和左邻居的正方形呈 L 形交叠，中间左上那块没人担保。左上邻居正是补上这块担保的，少一个都会把有洞的区域误判成实心正方形。

复杂度怎么算，实现上有哪些细节

每个格子只算一次、每次 O(1)，时间 O(m·n)；dp 表空间 O(m·n)。由于每格只依赖上一行和本行左边，可以用一维数组加一个变量缓存「左上」旧值，把空间压到 O(n)。

实现细节有三个：给 dp 表多加一圈全 0 的哨兵行列，首行首列就不用单独判边界；矩阵元素通常是字符 '1' 而不是数字 1，比较时别写错；最后返回 best × best 而不是 best。对照示例，那个 4×5 矩阵里最大边长是 3，答案是 9。

Python

def maximalSquare(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0]*(n+1) for _ in range(m+1)]
    best = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if matrix[i-1][j-1] == '1':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                best = max(best, dp[i][j])
    return best * best

C++

int maximalSquare(vector<vector<char>>& mat){
    int m = mat.size(), n = mat[0].size(), best = 0;
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
        if(mat[i-1][j-1]=='1'){
            dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            best = max(best, dp[i][j]);
        }
    return best * best;
}

Java

public int maximalSquare(char[][] mat) {
    int m = mat.length, n = mat[0].length, best = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (mat[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                best = Math.max(best, dp[i][j]);
            }
    return best * best;
}