LeetCode 1277. 统计全为 1 的正方形子矩阵

2025-09-16 HGNULB 约 10 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1277. 统计全为 1 的正方形子矩阵

题意分析

给一个 0-1 矩阵，数一数其中有多少个「正方形子矩阵且内部全是 1」。子矩阵按位置区分，边长为 1 的单个格子也算一个正方形，所以每个值为 1 的格子至少贡献一个。

注意统计的是数目而不是最大边长，也不要求正方形互不重叠——同一片 1 区域里，大正方形和它内部的小正方形都要各自计数。

「正方形」这个限制比「矩形」强得多：宽高必须相等，因此一个正方形能否成立，可以只用一个参数（边长）来刻画，这是本题能做到线性的根本原因。

矩阵行列都不超过 300，格子总数不到 $9 \times 10^4$；而所有正方形的数目上界大约是 $\sum_{k} (m-k+1)(n-k+1)$，量级在千万以内，用 32 位整型统计是安全的。空矩阵不会出现，题目保证至少一行一列。

解法：右下角动态规划

核心思路

暴力做法是枚举正方形的左上角和边长，再逐格验证内部是否全为 1，代价是 $O(m n \min(m,n)^2)$，$300 \times 300$ 的矩阵下就要上百亿次操作。改成二维前缀和可以把验证降到 $O(1)$，总代价 $O(mn\min(m,n))$，能过但仍不是最优。

真正的突破口是换一个统计口径：不按「左上角 + 边长」枚举，而是按右下角归类。每个全 1 正方形有唯一的右下角，所以答案等于「以每个格子为右下角的全 1 正方形个数」之和，互不重复也不遗漏。

接着观察一个关键性质：以 $(i,j)$ 为右下角的全 1 正方形，边长可以取 $1, 2, \dots, L$，其中 $L$ 是能取到的最大边长，而且中间不会断档——因为边长为 $k$ 的正方形一定包含边长为 $k-1$ 的那个。于是「个数」和「最大边长」是同一个数，只要算出 $L$ 就直接得到贡献。

状态定义：$dp[i][j]$ 表示以 $(i,j)$ 为右下角的全 1 正方形的最大边长。转移是：若 $matrix[i][j] = 0$ 则 $dp[i][j] = 0$；否则 $dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) + 1$。

为什么是三者取最小再加一？想让 $(i,j)$ 为右下角的正方形边长达到 $k$，需要它正上方能撑起边长 $k-1$（保证右侧那一竖列够长）、正左方能撑起 $k-1$（保证下方那一横行够长）、左上方也能撑起 $k-1$（保证中间那块方形是满的）。三个条件缺一不可，所以取最小；任一为 $t$ 时最多只能撑到 $t+1$，这个上界也是可达的，故等号成立。

答案就是把所有 $dp[i][j]$ 加起来。由于转移只用到上一行和当前行左侧，可以把二维表压成一维滚动数组，额外用一个变量 leftUp 手工保存被覆盖前的左上角旧值。

解题步骤

开长度为 $n+1$ 的一维数组 dp，下标从 1 开始使用，第 0 位当哨兵恒为 0。加哨兵列是为了让第一列的 dp[j-1] 有值可读，省掉一整套边界判断。

行循环 i 从 1 到 $m$，列循环 j 从 1 到 $n$，对应的原矩阵格子是 matrix[i-1][j-1]。整体下标偏移一位，是哨兵带来的必然代价。

每行开头把 leftUp 置 0。它的语义是「上一行、上一列」那个格子的 dp 值；处理每行第一列时，左上角落在哨兵列外，理应为 0。

进入格子后第一件事是 upper = dp[j]，把这一格被覆盖前的旧值（即上一行同列的 dp）暂存下来。必须在写入之前保存，因为写完就再也拿不到了。

若 matrix[i-1][j-1] == 1，取 dp[j]（上方）、dp[j-1]（左方，本行已更新）、leftUp（左上方）三者最小加一写回 dp[j]，并把这个值累加进答案。注意此时 dp[j] 还是旧值代表上方，dp[j-1] 已是新值代表左方，滚动数组的这种「半新半旧」正是它能工作的原因。

若当前格子是 0，直接把 dp[j] 清零。不能跳过不写，否则上一行的残值会被下一行误当成本行的结果。

循环末尾执行 leftUp = upper，把刚才暂存的旧值交给下一列当左上角。这一行必须放在整个格子处理的最后，且无论走哪个分支都要执行。

以 matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]] 走一遍（$m = 3$、$n = 4$，dp 初始为 $[0,0,0,0,0]$）：

第一行 [0,1,1,1]，leftUp = 0。$j=1$ 格子是 0，dp[1] 置 0。$j=2$ 格子是 1，三者是 dp[2]=0、dp[1]=0、leftUp=0，最小值 0 加一得 1，dp[2]=1，答案累计 1。$j=3$ 同理得 dp[3]=1，累计 2。$j=4$ 得 dp[4]=1，累计 3。此时 dp = [0,0,1,1,1]，符合直觉：第一行的三个 1 各自只能撑起边长 1 的正方形。

第二行 [1,1,1,1]，leftUp 重置为 0。$j=1$：upper = 0，格子是 1，三者是 dp[1]=0、dp[0]=0、leftUp=0，得 dp[1]=1，累计 4，随后 leftUp = 0。$j=2$：upper = dp[2] = 1，格子是 1，三者是 dp[2]=1（上方）、dp[1]=1（左方）、leftUp=0（左上是第一行第一列的 0），最小值 0 加一仍是 1，dp[2]=1，累计 5，leftUp 变 1。$j=3$：upper = dp[3] = 1，三者是 1、1、1，最小 1 加一得 dp[3]=2，累计 7，leftUp 变 1。$j=4$：upper = dp[4] = 1，三者是 dp[4]=1、dp[3]=2、leftUp=1，最小 1 加一得 dp[4]=2，累计 9，leftUp 变 1。此时 dp = [0,1,1,2,2]。

第三行 [0,1,1,1]，leftUp 重置为 0。$j=1$：upper = dp[1] = 1，格子是 0，dp[1] 清零，leftUp 变 1。$j=2$：upper = dp[2] = 1，格子是 1，三者是 dp[2]=1、dp[1]=0、leftUp=1，最小 0 加一得 dp[2]=1，累计 10，leftUp 变 1。$j=3$：upper = dp[3] = 2，三者是 2、1、1，最小 1 加一得 dp[3]=2，累计 12，leftUp 变 2。$j=4$：upper = dp[4] = 2，三者是 dp[4]=2、dp[3]=2、leftUp=2，最小 2 加一得 dp[4]=3，累计 15，leftUp 变 2。

最终答案 15。拆开看是：边长 1 的正方形 10 个（矩阵里共有 10 个 1），边长 2 的 4 个，边长 3 的 1 个，合计 $10 + 4 + 1 = 15$，与逐格 dp 求和的结果一致。

代码实现

class Solution {
    // 若当前格子为 1，新的正方形必须同时依赖上方、左方、左上方三个方向的较小边长。
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] dp = new int[n + 1];
        int res = 0;

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

                leftUp = upper;
            }
        }

        return res;
    }
}

func countSquares(matrix [][]int) int {
    // 若当前格子为 1，新的正方形必须同时依赖上方、左方、左上方三个方向的较小边长。
    m, n := len(matrix), len(matrix[0])
    dp := make([]int, n+1)
    res := 0

    for i := 1; i <= m; i++ {
        leftUp := 0
        for j := 1; j <= n; j++ {
            upper := dp[j]
            if matrix[i-1][j-1] == 1 {
                minVal := dp[j]
                if dp[j-1] < minVal {
                    minVal = dp[j-1]
                }
                if leftUp < minVal {
                    minVal = leftUp
                }
                dp[j] = minVal + 1
                res += dp[j]
            } else {
                dp[j] = 0
            }

            leftUp = upper
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(mn)$，每个格子只被处理一次，格内是三次比较加一次累加的常数操作。

空间复杂度：$O(n)$，一维滚动数组长度为 $n+1$，外加 leftUp、upper 两个标量；若允许原地改写输入矩阵，可以进一步降到 $O(1)$ 额外空间。

关键点总结

统计「某种子结构的数目」时，先给每个子结构找一个唯一的代表位置（这题是右下角），把总数拆成各位置贡献之和，是最常见的去重手法。

边长可取值连续不断档，使得「最大边长」直接等于「个数」。这一步的观察省掉了另开一张计数表，也是本题只用一个 dp 值就能收工的关键。

三方向取最小加一的转移，本质是三个必要条件同时成立；能讲出「上方管右列、左方管下行、左上方管中间那块」这层几何含义，比死记公式牢靠得多。

滚动数组的正确性依赖「半新半旧」：同一轮里 dp[j] 尚未更新代表上一行，dp[j-1] 已更新代表本行左侧，而左上角必须用额外变量在覆盖前抢救出来。

面试视角：这题和 221 最大正方形共用同一张 dp 表，区别只在于一个取 max 一个取 sum。面试时先点明这层关系，再解释为什么求和就是答案，能非常快地建立可信度；接着常见的追问是「改成统计全 1 矩形怎么办」，那就要换成按行压缩加单调栈的思路了。

易错点总结

错误写法：把 dp[i][j] 直接当答案取最大值而不是求和 → matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]] 会输出最大边长 3，而正确答案是正方形总数 15。

错误写法：转移写成 min(上, 左) + 1，漏掉左上角：matrix = [[1,1],[1,0]] 之后再加一行一列这类情形下，缺失的左上角会让 dp 高估；最直观的反例是 matrix = [[0,1],[1,1]]，右下角的上方和左方都是 1，取 min 得 1 加一为 2，但左上角是 0，边长为 2 的正方形并不存在，正确的 dp 值应为 1，答案会从 3 被算成 4。

错误写法：当前格子为 0 时跳过不写 dp[j] → 滚动数组里残留的是上一行的值，下一行会把它当成本行的上方状态，凭空长出不存在的正方形。

错误写法：leftUp 在写入 dp[j] 之后才保存，即 upper = dp[j] 放在更新语句下面 → 保存到的是本行新值而非上一行旧值，左上角信息全错，dp 普遍偏大。

错误写法：每行开头忘记把 leftUp 归零 → 上一行最后一列的值被带到本行第一列当左上角，最左侧一列的 dp 被高估。

错误写法：leftUp = upper 只写在 matrix[i-1][j-1] == 1 的分支里 → 遇到 0 的格子时 leftUp 不更新，后续列拿到的左上角错位一格甚至更远。

错误写法：不加哨兵列、直接用 0 到 $n-1$ 的下标，却忘了给 $j = 0$ 单独处理 → 访问 dp[-1] 越界；本题的哨兵设计正是为了消除这类特判。

错误写法：把矩阵下标写成 matrix[i][j] 而没有减一 → 带哨兵后循环变量从 1 起步，直接用会读到下一行下一列的数据并在最后一轮越界。

错误写法：认为「边长为 $k$ 的正方形存在就必然存在边长 $k-1$ 的」这句话反过来也成立，从而按 dp 值倒推时重复计数 → 贡献恰好是 dp 值本身，既不是 dp 值的平方也不是累加求和后再乘系数。

相似题目

题目	难度	考察点
221. 最大正方形	中等	同一张 dp 表，取最大值并返回面积而不是累加个数
1504. 统计全 1 子矩形	中等	放宽到矩形后边长不再等价于个数，需按列高度配合单调栈统计
85. 最大矩形	困难	逐行压缩成柱状图，再对每一行跑一次最大矩形
84. 柱状图中最大的矩形	困难	一维版本，单调栈求每根柱子向两侧能扩展的边界
1139. 最大的以 1 为边界的正方形	中等	只要求边框全为 1，需预处理每格向左、向上的连续 1 长度
695. 岛屿的最大面积	中等	同为 0-1 矩阵，但统计的是连通块而非规则形状，改用搜索