LeetCode 1277 统计全 1 正方形子矩阵：枚举边界、动态规划与单调栈三种解法全解——基于 codeforces-go 仓库题解剖析

• 科学计算

导读

本文以 leetcode/weekly/165/c/1277.md 为核心，完整剖析「统计全 1 正方形子矩阵」这一经典二维矩阵计数问题（LeetCode 1277 countSquares）。文档提供了三种从易到难的解法：枚举正方形上下边界（O(m²n)）、动态规划（O(mn)）与单调栈贡献法（O(mn)），并给出 Python3 / Java / C++ / Go 四语言实现。我们将逐条继承文档的核心推导与全部代码，并结合仓库中的配套实现 c.go、测试用例 c_test.go 与通用测试框架 leetcode.go 进行源码级印证，帮助你彻底吃透「子矩形计数」一类问题的通用套路。

问题概述

给定一个m × n的二进制矩阵matrix（元素为 0 或 1），统计其中全部由 1 组成的正方形子矩阵的个数。子矩阵必须是正方形，且边长可以为任意正整数。

以文档中的示例 1 为例：

[[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]]

答案应为 15（大小为 1 的正方形 10 个、大小为 2 的正方形 4 个、大小为 3 的正方形 1 个）。仓库测试用例 c_test.go 中的两组样例正是该矩阵（输出 15）以及[[1,0,1],[1,1,0],[1,1,0]]（输出 7）。

下面分别展开文档给出的三种方法。

方法一：枚举正方形的上下边界（O(m²n)）

核心思想：把二维问题压缩成一维

枚举正方形的上边界top与下边界bottom，统计每一列 1 的个数，把原二维问题「压缩」为一维数组上的问题。

回到示例 1。假设枚举到上边界为第 0 行、下边界为第 1 行，即矩阵的前两行，此时正方形的高固定为h = 2。统计每一列 1 的个数，得到一个一维数组：

a = [1, 2, 2, 2]

由于全 1 正方形的每一列都必须是 1，所以长度为h的合法子数组，其每一项都必须是h。问题于是转化为：

统计数组a中长度恰好为h、且每一项都等于h的子数组的数目。

这与 LeetCode2348（全 0 子数组的数目）的思路同源：在一维数组中统计满足「连续一段全为某值」的子数组个数，用「上一个不合法的位置」即可在线性时间内完成统计。

增量更新技巧

代码实现时，外层循环枚举上边界，内层循环枚举下边界。当下边界bottom加一时，只需把每个a[j]都累加上matrix[bottom][j]，无需对整个数组重新统计，从而把每一轮统计的复杂度维持在 O(n)。

扫描列下标j时维护last：记录上一个a[j] != h的位置。若当前a[j] == h且j - last >= h，说明以j为右端点、长度为h的子数组内没有任何「非 h」元素（即全部等于 h），答案加一。

四语言实现

class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) ans = 0 for top in range(m): # 枚举上边界 a = [0] * n for bottom in range(top, m): # 枚举下边界 h = bottom - top + 1 # 高 # 2348. 全 h 子数组的数目 last = -1 for j in range(n): a[j] += matrix[bottom][j] # 把 bottom 这一行的值加到 a 中 if a[j] != h: last = j # 记录上一个非 h 元素的位置 elif j - last >= h: # 右端点为 j 的长为 h 的子数组全是 h ans += 1 return ans

class Solution { public int countSquares(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int ans = 0; for (int top = 0; top < m; top++) { // 枚举上边界 int[] a = new int[n]; for (int bottom = top; bottom < m; bottom++) { // 枚举下边界 int h = bottom - top + 1; // 高 // 2348. 全 h 子数组的数目 int last = -1; for (int j = 0; j < n; j++) { a[j] += matrix[bottom][j]; // 把 bottom 这一行的值加到 a 中 if (a[j] != h) { last = j; // 记录上一个非 h 元素的位置 } else if (j - last >= h) { // 右端点为 j 的长为 h 的子数组全是 h ans++; } } } } return ans; } }

class Solution { public: int countSquares(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); int ans = 0; for (int top = 0; top < m; top++) { // 枚举上边界 vector<int> a(n); for (int bottom = top; bottom < m; bottom++) { // 枚举下边界 int h = bottom - top + 1; // 高 // 2348. 全 h 子数组的数目 int last = -1; for (int j = 0; j < n; j++) { a[j] += matrix[bottom][j]; // 把 bottom 这一行的值加到 a 中 if (a[j] != h) { last = j; // 记录上一个非 h 元素的位置 } else if (j - last >= h) { // 右端点为 j 的长为 h 的子数组全是 h ans++; } } } } return ans; } };

func countSquares(matrix [][]int) (ans int) { m, n := len(matrix), len(matrix[0]) for top := range m { // 枚举上边界 a := make([]int, n) for bottom := top; bottom < m; bottom++ { // 枚举下边界 h := bottom - top + 1 // 高 // 2348. 全 h 子数组的数目 last := -1 for j := range n { a[j] += matrix[bottom][j] // 把 bottom 这一行的值加到 a 中 if a[j] != h { last = j // 记录上一个非 h 元素的位置 } else if j-last >= h { // 右端点为 j 的长为 h 的子数组全是 h ans++ } } } } return }

复杂度分析

• 时间复杂度：O(m²n)，其中 m、n 分别为 matrix 的行数和列数。上下边界各 O(m) 种组合，每轮扫描 n 列。
• 空间复杂度：O(n)，仅需一维数组a。

方法二：动态规划（O(mn)）

关键结论：正方形个数等价于正方形最大边长

定义f[i][j]为右下角在(i, j)的全 1 正方形的最大边长。那么对于以(i, j)为右下角的所有正方形，边长分别可取 1 到f[i][j]，因此以该点为右下角的正方形个数恰好等于f[i][j]。整个矩阵中全 1 正方形的总数，就等于所有f[i][j]之和。

这一「个数等于最大边长」的结论是本题 DP 解法最巧妙的一步：把「计数」问题转化为「求最大边长」问题。

状态转移方程

若matrix[i][j] = 0，则f[i][j] = 0（不可能有以它为右下角的全 1 正方形）；若matrix[i][j] = 1，则其最大边长由左上、上、左三个方向的邻居共同决定：

f[i][j] = 0, matrix[i][j] = 0 f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1, matrix[i][j] = 1

直观理解：右下角在(i,j)、边长为k的全 1 正方形，要求(i-1,j-1)、(i-1,j)、(i,j-1)三处都能容纳边长至少k-1的全 1 正方形，故取三者最小值再加一。

边界处理：加一行一列 0

当i = 0或j = 0时，转移方程会出现负下标-1。为避免负数下标，在f矩阵的最上边添加一行 0、最左边添加一列 0，对应下标出界的状态（其正方形最大边长为 0）。由于修改了f的坐标，转移方程中f的下标要整体加一，而matrix的下标保持不变（我们只是在f的上边和左边插入了 0）：

f[i+1][j+1] = 0, matrix[i][j] = 0 f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1, matrix[i][j] = 1

初始值f[0][j] = f[i][0] = 0。最终答案即为整个f矩阵的元素和。

优化前：二维 DP 数组

class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) f = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(matrix): for j, x in enumerate(row): if x: f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1 return sum(map(sum, f))

class Solution { public int countSquares(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int[][] f = new int[m + 1][n + 1]; int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] > 0) { f[i + 1][j + 1] = Math.min(Math.min(f[i][j], f[i][j + 1]), f[i + 1][j]) + 1; ans += f[i + 1][j + 1]; } } } return ans; } }

class Solution { public: int countSquares(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector f(m + 1, vector<int>(n + 1)); int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j]) { f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1; ans += f[i + 1][j + 1]; } } } return ans; } };

func countSquares(matrix [][]int) (ans int) { m, n := len(matrix), len(matrix[0]) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) } for i, row := range matrix { for j, x := range row { if x > 0 { f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1 ans += f[i+1][j+1] } } } return }

优化：原地修改，把 matrix 当作 f

仔细观察转移方程可以发现：计算f[i+1][j+1]只用到了f[i][j]、f[i][j+1]、f[i+1][j]（即当前点左上、上方、左方），且行主序遍历时这三个位置都已被计算完毕。因此可以直接把matrix当作f原地修改，无需额外数组，空间降到 O(1)：

class Solution: def countSquares(self, matrix: List[List[int]]) -> int: for i, row in enumerate(matrix): for j, x in enumerate(row): if x and i and j: row[j] += min(matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]) return sum(map(sum, matrix))

class Solution { public int countSquares(int[][] matrix) { int ans = 0; for (int i = 0; i < matrix.length; i++) { int[] row = matrix[i]; for (int j = 0; j < row.length; j++) { if (row[j] > 0 && i > 0 && j > 0) { row[j] += Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), row[j - 1]); } ans += row[j]; } } return ans; } }

class Solution { public: int countSquares(vector<vector<int>>& matrix) { int ans = 0; for (int i = 0; i < matrix.size(); i++) { auto& row = matrix[i]; for (int j = 0; j < row.size(); j++) { if (i && j && row[j]) { row[j] += min({matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]}); } ans += row[j]; } } return ans; } };

func countSquares(matrix [][]int) (ans int) { for i, row := range matrix { for j, x := range row { if x > 0 && i > 0 && j > 0 { row[j] += min(matrix[i-1][j], matrix[i-1][j-1], row[j-1]) } ans += row[j] } } return }

复杂度分析

• 时间复杂度：O(mn)，其中 m、n 分别为 matrix 的行数和列数。
• 空间复杂度：优化前 O(mn)，优化后 O(1)（原地修改，无额外空间）。

提示：转移方程的思路与「二维前缀和」的推导方式类似，文档建议读者先学习二维前缀和，有助于独立推导出本题的转移方程。

方法三：单调栈（O(mn)）

前置：从「最大矩形」到「正方形计数」

方法三建立在经典问题之上，文档建议先完成 85. 最大矩形（本质是 84. 柱状图中最大的矩形 + 逐行维护柱子高度）。核心观察：

在宽度为w的空间内，有w - k + 1个不同位置可以放边长为k的正方形。

逐行维护柱子高度

把矩阵逐行扫描，维护一个高度数组heights：遇到1则高度加一（柱子在竖直方向连续累加），遇到0则清零。每处理完一行，就在当前heights上统计一次「该行作为底边时能形成的正方形个数」，累加即为答案。

heights末尾额外补一个 0（哨兵），保证扫描结束时栈中所有柱子都能被弹出结算——这正是 84 题解法中的经典技巧。

单个柱子的贡献：边长下界与上界

对于某个高度为h的柱子，设其对应的矩形底边长为：

w = heights[r] - heights[l] + 1

其中heights[l]是h左侧高度小于 h 的最近柱子（没有则为 0），heights[r]是h右侧高度小于 h 的最近柱子（没有则为 n）。注意文档给出的等式中l、r是指针位置关系，代码实现中w = r - l - 1（用当前右边界下标减去左边界下标再减 1），两者等价。

在该柱子对应的矩形区域[l+1, r-1]内，可容纳的正方形边长受两个方向约束：

• 下界lower = max(heights[l], heights[r]) + 1：边长为k时，宽方向上必须能横跨连续的k个位置，而左右两侧高度小于h的柱子会打断这种连续；
• 上界upper = min(h, w)：正方形不能超出柱子高度，也不能超出矩形底边宽度。

贡献求和公式

枚举正方形边长k = lower, lower+1, …, upper，每个边长k贡献w - k + 1个位置，于是高度为h的柱子对答案的总贡献为：

sum_{k=lower}^{upper} (w - k + 1) = ((2w + 2 - lower - upper) * (upper - lower + 1)) / 2

这是一个首项为w - lower + 1、末项为w - upper + 1的等差数列求和，可直接用公式 O(1) 算出，无需逐个边长枚举。

哨兵 -1 的作用

单调栈中压入哨兵-1：当栈中只有一个数时，栈顶「下面那个数」就是-1，对应left[i] = -1（左侧不存在更矮柱子）的情况，统一了边界处理。

四语言实现

class Solution: def solve(self, heights: List[int]) -> int: st = [-1] # 哨兵：在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况 ans = 0 for r, hr in enumerate(heights): while len(st) > 1 and heights[st[-1]] >= hr: h = heights[st.pop()] # 矩形的高 l = st[-1] # 栈顶下面那个数就是 l w = r - l - 1 upper = min(h, w) lower = (hr if l < 0 else max(heights[l], hr)) + 1 if lower <= upper: ans += (w * 2 + 2 - lower - upper) * (upper - lower + 1) // 2 st.append(r) return ans def countSquares(self, matrix: List[List[int]]) -> int: heights = [0] * (len(matrix[0]) + 1) # 末尾多一个 0，理由见 84 题题解 ans = 0 for row in matrix: # 计算底边为 row 的柱子高度 for j, x in enumerate(row): if x == 0: heights[j] = 0 # 柱子高度为 0 else: heights[j] += 1 # 柱子高度加一 ans += self.solve(heights) return ans

class Solution { public int countSquares(int[][] matrix) { int n = matrix[0].length; int[] heights = new int[n + 1]; // 末尾多一个 0，理由见 84 题题解 int ans = 0; for (int[] row : matrix) { // 计算底边为 row 的柱子高度 for (int j = 0; j < n; j++) { int x = row[j]; if (x == 0) { heights[j] = 0; // 柱子高度为 0 } else { heights[j]++; // 柱子高度加一 } } ans += solve(heights); } return ans; } private int solve(int[] heights) { Deque<Integer> st = new ArrayDeque<>(); st.push(-1); // 哨兵：在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况 int ans = 0; for (int r = 0; r < heights.length; r++) { int hr = heights[r]; while (st.size() > 1 && heights[st.peek()] >= hr) { int h = heights[st.pop()]; // 矩形的高 int l = st.peek(); // 栈顶下面那个数就是 l int w = r - l - 1; int upper = Math.min(h, w); int lower = (l < 0 ? hr : Math.max(heights[l], hr)) + 1; if (lower <= upper) { ans += (w * 2 + 2 - lower - upper) * (upper - lower + 1) / 2; } } st.push(r); } return ans; } }

class Solution { int solve(vector<int>& heights) { stack<int> st; st.push(-1); // 哨兵：在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况 int ans = 0; for (int r = 0; r < heights.size(); r++) { int hr = heights[r]; while (st.size() > 1 && heights[st.top()] >= hr) { int h = heights[st.top()]; // 矩形的高 st.pop(); int l = st.top(); // 栈顶下面那个数就是 l int w = r - l - 1; int upper = min(h, w); int lower = (l < 0 ? hr : max(heights[l], hr)) + 1; if (lower <= upper) { ans += (w * 2 + 2 - lower - upper) * (upper - lower + 1) / 2; } } st.push(r); } return ans; } public: int countSquares(vector<vector<int>>& matrix) { int n = matrix[0].size(); vector<int> heights(n + 1); // 末尾多一个 0，理由见 84 题题解 int ans = 0; for (auto& row : matrix) { // 计算底边为 row 的柱子高度 for (int j = 0; j < n; j++) { int x = row[j]; if (x == 0) { heights[j] = 0; // 柱子高度为 0 } else { heights[j]++; // 柱子高度加一 } } ans += solve(heights); } return ans; } };

func solve(heights []int) (ans int) { st := []int{-1} // 哨兵：在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况 for r, hr := range heights { for len(st) > 1 && heights[st[len(st)-1]] >= hr { h := heights[st[len(st)-1]] // 矩形的高 st = st[:len(st)-1] l := st[len(st)-1] // 栈顶下面那个数就是 l w := r - l - 1 upper := min(h, w) lower := hr + 1 if l >= 0 { lower = max(heights[l], hr) + 1 } if lower <= upper { ans += (w*2 + 2 - lower - upper) * (upper - lower + 1) / 2 } } st = append(st, r) } return } func countSquares(matrix [][]int) (ans int) { heights := make([]int, len(matrix[0])+1) // 末尾多一个 0，理由见 84 题题解 for _, row := range matrix { // 计算底边为 row 的柱子高度 for j, x := range row { if x == 0 { heights[j] = 0 // 柱子高度为 0 } else { heights[j]++ // 柱子高度加一 } } ans += solve(heights) } return }

复杂度分析

• 时间复杂度：O(mn)，其中 m、n 分别为 matrix 的行数和列数。逐行更新高度 O(n)，每行调用一次单调栈统计 O(n)，每个元素至多入栈、出栈各一次。
• 空间复杂度：O(n)，heights数组与单调栈均为一维。

仓库配套实现与测试验证

本题在仓库中位于 leetcode/weekly/165/c/c.go，文件内共存了四种 Go 实现，非常适合横向对照：

其中countSquares0使用二维前缀和加速子矩阵求和，再对每个左上角暴力扩张边长sz，只要query(i, j, i+sz, j+sz) == sz*sz（子矩阵全 1）就计数并继续扩张。它虽然复杂度更高，但逻辑直观，适合作为对拍/对照的基准实现——这也体现了仓库「一题多解、互相印证」的整理风格。

测试方面，c_test.go 由仓库的generator_test生成，通过调用通用测试框架 leetcode.go 中的RunLeetCodeFunc，将函数countSquares与两组样例输入输出绑定执行。测试框架内部使用反射自动匹配输入输出格式并逐一断言，运行方式为在目录下执行：

go test ./leetcode/weekly/165/c

若在本文档对应的解题目录下直接运行测试，输出为Current test is [c]并确认两组样例均通过（对应输出 15 与 7）。

另外，单调栈的通用模板（左右最近更小元素、贡献法）在 copypasta/monotone_stack.go 中有完整封装：其使用栈底哨兵-1、以「严格小于 / 小于等于」区分重复元素处理、并在注释中解释了「元素最多入栈出栈各一次」从而整体 O(n) 的原理。方法三的solve本质就是该模板在「统计正方形贡献」场景下的应用，可一并阅读加深理解。

三种方法对比总结

从源码结构与文档编排看，本题属于「子矩形 DP」与「单调栈矩形面积/贡献法」两大专题的交叉题。文档给出的专题训练建议为：动态规划题单中的「子矩形 DP」部分，以及单调栈题单中的「矩形」部分。若想继续深化，可顺藤摸瓜练习同一主题下的最大矩形（85）、柱状图最大矩形（84）、全 0 子数组计数（2348）以及二维前缀和（304）等关联题目，形成完整的知识闭环。

• 科学计算