科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/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 ansclass 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(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); int ans 0; for (int top 0; top m; top) { // 枚举上边界 vectorint 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的上边和左边插入了 0f[i1][j1] 0, matrix[i][j] 0 f[i1][j1] min(f[i][j], f[i][j1], f[i1][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(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); vector f(m 1, vectorint(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, m1) for i : range f { f[i] make([]int, n1) } for i, row : range matrix { for j, x : range row { if x 0 { f[i1][j1] min(f[i][j], f[i][j1], f[i1][j]) 1 ans f[i1][j1] } } } return }优化原地修改把 matrix 当作 f仔细观察转移方程可以发现计算f[i1][j1]只用到了f[i][j]、f[i][j1]、f[i1][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(vectorvectorint 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 的最近柱子没有则为 0heights[r]是h右侧高度小于 h 的最近柱子没有则为 n。注意文档给出的等式中l、r是指针位置关系代码实现中w r - l - 1用当前右边界下标减去左边界下标再减 1两者等价。在该柱子对应的矩形区域[l1, r-1]内可容纳的正方形边长受两个方向约束下界lower max(heights[l], heights[r]) 1边长为k时宽方向上必须能横跨连续的k个位置而左右两侧高度小于h的柱子会打断这种连续上界upper min(h, w)正方形不能超出柱子高度也不能超出矩形底边宽度。贡献求和公式枚举正方形边长k lower, lower1, …, upper每个边长k贡献w - k 1个位置于是高度为h的柱子对答案的总贡献为sum_{klower}^{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 ansclass 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) { DequeInteger 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(vectorint heights) { stackint 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(vectorvectorint matrix) { int n matrix[0].size(); vectorint 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二维前缀和 暴力枚举边长对照参考c.go#L3-L23countSquares1方法一枚举上下边界c.go#L25-L44countSquares2方法二原地 DPc.go#L46-L56countSquares含countSquare方法三单调栈c.go#L58-L94其中countSquares0使用二维前缀和加速子矩阵求和再对每个左上角暴力扩张边长sz只要query(i, j, isz, jsz) 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本质就是该模板在「统计正方形贡献」场景下的应用可一并阅读加深理解。三种方法对比总结方法核心思路时间复杂度空间复杂度适用场景枚举上下边界二维压缩为一维统计全 h 子数组O(m²n)O(n)行数 m 较小时直观易写动态规划最大边长 正方形个数转移取三方 minO(mn)O(mn)原地可 O(1)通用最优解最推荐掌握单调栈逐行维护柱子高度按边长上下界做等差数列求和O(mn)O(n)需要与 84/85 题体系打通时从源码结构与文档编排看本题属于「子矩形 DP」与「单调栈矩形面积/贡献法」两大专题的交叉题。文档给出的专题训练建议为动态规划题单中的「子矩形 DP」部分以及单调栈题单中的「矩形」部分。若想继续深化可顺藤摸瓜练习同一主题下的最大矩形85、柱状图最大矩形84、全 0 子数组计数2348以及二维前缀和304等关联题目形成完整的知识闭环。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode-Go 题解509. Fibonacci Number 七种 Go 解法全解析递归、动态规划、矩阵快速幂与通项公式LeetCode Go 题解509. Fibonacci Number 七种 Go 解法全解析递归、动态规划、矩阵快速幂与通项公式 导读 本文以 Leet示例工程LeetCode 2348 全零子数组计数四种解法与源码实现剖析基于 leetcode 仓库LeetCode 2348 全零子数组计数四种解法与源码实现剖析基于 leetcode 仓库 本文基于 articles/number of zero f示例工程教程LeetCode 0085 最大矩形题解AlgoNote 中「动态规划 单调栈」将二维矩阵转化为一维直方图LeetCode 0085 最大矩形题解AlgoNote 中「动态规划 单调栈」将二维矩阵转化为一维直方图 本篇基于 AlgoNote算法通关手册题解教程文档知识库上一篇Antigen问题排查工作坊实战解决复杂使用难题下一篇如何快速训练AI智能体Agent Lightning完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考