LeetCode 1292：二维前缀和与二分答案优化枚举，求解最大正方形

第一次在 LeetCode 上看到 1292 这道题时我的第一反应是这不就是二维前缀和的模板题吗但真正动手写之后才发现前缀和只是基础真正的考点是后面那四个字——枚举优化。题目要求在一个 m x n 的矩阵中找到一个正方形区域使得区域内所有元素之和不大于给定的 threshold然后返回这个正方形的最大边长。朴素做法需要把正方形的位置和边长全部枚举一遍复杂度非常吓人。这篇文章我就从暴力解法讲起逐步优化到二分答案把前缀和、枚举优化这两个核心关键词彻底讲透同时把我在写代码时踩过的坑一并分享出来希望对你刷题和准备面试都有帮助。1. 题目到底在问什么先读懂“最大边长”这个约束1.1 题干里的三个关键信息给定一个 m 行 n 列的矩阵 mat和一个整数 threshold要求返回元素总和小于等于阈值的正方形区域的最大边长。如果不存在这样的正方形则返回 0。翻译成人话就是三步选一个正方形算这个正方形里所有数的和看这个和有没有超过 threshold。没超过就记下边长最后在所有满足条件的正方形里取边长最大的那个。这里有几个容易被忽略的细节。第一个正方形的边必须和矩阵的边平行不能斜着放。第二个“最大边长”意味着不是找到第一个满足条件的就停而要在所有可行解里取最大值。第三个如果矩阵里最小的格子都比 threshold 大那就没有任何边长为 1 的正方形满足条件直接返回 0。这三个细节看起来简单但实际写代码时很容易在边界条件上翻车尤其是第三个。比如 threshold 是 0而矩阵元素全是正整数那答案必然是 0很多人在测试用例里看到这种情况才想起来要处理。1.2 为什么暴力解法会超时先别急着写代码做个复杂度推导。如果完全不用任何技巧枚举每一个左上角位置需要 O(mn)枚举边长 k 需要 O(min(m,n))对每个正方形求和又需要 O(k²)。三层嵌套下来总复杂度是 O(mn · min(m,n)³)这已经不是一个能看的数字了。就算用上最基础的前缀和优化把“求正方形内元素和”这一步从 O(k²) 降到 O(1)整个算法的复杂度依然有 O(mn · min(m,n))。在 m 和 n 都接近 300 的情况下就是 300×300×300 ≈ 2700 万次操作勉强能跑但如果矩阵再大一点或者面试官让你继续优化这种写法就不够看了。所以这道题真正考察的能力是你知不知道在枚举过程中哪里是可以被优化的。答案很明确——边长 k 的枚举过程是可以被优化的因为它是单调的。2. 前缀和把“反复求和”变成“一次查表”2.1 一维前缀和回顾在讲二维前缀和之前先回顾一下一维前缀和。给定一个数组 arr我们可以预处理出一个前缀和数组 pre其中 pre[i] 表示 arr[0] 到 arr[i-1] 的和。这样要求任意区间 [l, r] 的和只需要计算 pre[r1] - pre[l] 即可。为什么能这样做因为前缀和本质上是一种“空间换时间”的思想用 O(n) 的预处理时间换来 O(1) 的区间查询时间。这个思想在算法题里太常用了从一维数组的子区间求和到树上的路径求和再到这道题的二维矩阵求和都是同一个套路。2.2 二维前缀和的构建公式二维前缀和就是把一维前缀和扩展一个维度。定义 pre[i][j] 表示矩阵左上角 (0,0) 到 (i-1,j-1) 这个子矩阵的所有元素之和。注意这里的索引偏移是为了后续写代码方便。构建过程有一个经典公式pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] mat[i-1][j-1]这个公式看起来有点绕我用一个生活化的方式来解释。假设你要计算一个班级所有学生的总分而这个班级可以分成几个小组。pre[i-1][j] 是“上面那些组”的总分pre[i][j-1] 是“左边那些组”的总分两个加起来之后左上角那个小方阵被算了两次所以要减掉一次 pre[i-1][j-1]最后再加上当前格子 mat[i-1][j-1] 本身的分数。这个过程用术语说叫“容斥原理”但在写代码的时候你不需要背这个名词只需要记住加上上面的加上左边的减掉左上角的最后加上自己。2.3 任意子矩阵和怎么算有了前缀和数组求任意一个子矩阵 (r1, c1) 到 (r2, c2) 的元素和也是一个固定的公式sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]这个公式的原理和构建时一样都是容斥。想象一个大矩形它的元素和是 pre[r21][c21]。我们要挖掉上面一条也就是 pre[r1][c21]再挖掉左边一条也就是 pre[r21][c1]。但左上角那个小块被挖了两次所以要加回来一次 pre[r1][c1]。这里有一个很容易搞混的索引问题。一开始我写这个公式的时候总是纠结要不要加 1、要不要减 1后来总结出一个方法不管什么坐标你只要记住 pre[i][j] 表示的是“前 i 行前 j 列的和”然后把矩阵的边界代入进去就知道该在哪里加 1 了。2.4 索引偏移问题为什么我推荐 (m1) x (n1)既然 pre[i][j] 表示前 i 行前 j 列的和那么当 i0 或 j0 时pre 的值就应该是 0。这就是为什么我习惯把 pre 开成 (m1) x (n1)而不是和原矩阵一样大小。这样做最大的好处是不需要特判。如果 pre 和 mat 一样大那么计算 pre[0][0] 的时候就需要处理“pre[-1][0] 不存在”的问题计算子矩阵和的时候也要考虑 r10 或 c10 的边界情况。而多开一圈之后所有公式都统一了代码写起来非常清爽也减少了出 bug 的概率。提示这算是我个人的一个小习惯但确实帮我在大量二维前缀和题目里少踩了很多坑。建议新接触前缀和的朋友都试试这个写法等熟练之后再根据自己的习惯调整。3. 枚举优化的两条路二分答案与单调性分析3.1 单调性分析为什么边长越大矩阵和越大这道题能优化的关键在于一个单调性如果边长 k 的正方形已经满足条件那么边长小于 k 的正方形不一定满足但是反过来如果边长 k 的正方形不满足条件那么所有包含它的更大的正方形也一定不满足。为什么因为矩阵里的元素都是正数正方形变大意味着多加了若干正数总和只会增加不会减少。这个性质太重要了它意味着边长 k 的“可行性”是单调的存在一个分界点比它小的边长都可行比它大的边长都不可行。用生活类比就是你手里有一堆越来越重的哑铃5 公斤举得动6 公斤可能也举得动但到了 15 公斤突然举不动了那 16、17 公斤必然更举不动。你要找的就是那个最大的、还能举起来的重量。3.2 方案一二分边长把 O(min(m,n)) 变成 O(log)既然可行性是单调的那就可以用二分答案来枚举边长。二分的对象是边长 k区间是 [0, min(m,n)]。每次取中点 mid判断是否存在任意一个边长为 mid 的正方形其元素和小于等于 threshold。如果存在说明答案至少是 mid左边界移动到 mid如果不存在说明 mid 以及比 mid 更大的边长都不可能右边界移动到 mid-1。这样原本需要枚举 O(min(m,n)) 种边长现在只需要 O(log(min(m,n))) 次判断。每次判断要遍历所有可能的左上角位置复杂度是 O(mn)。所以整个算法的时间复杂度是 O(mn log(min(m,n)))。对比原来的 O(mn min(m,n))在 min(m,n)300 时大约快了 30 倍。3.3 方案二双指针/滑动窗口一个进阶方向除了二分还有一条更极致的优化路线用双指针或者滑动窗口做枚举优化理论上能把复杂度压到接近 O(mn)。大概思路是先固定正方形的上边界然后逐渐扩大下边界同时维护每列的前缀和把它们看成一个一维数组。在这个一维数组上用双指针维护一个“和不超过 threshold 的最长区间”这个区间长度就对应正方形边长。这个思路写起来要比二分复杂不少而且边界情况更多。对我来说在面试场景下先把二分解法写出来、讲清楚单调性已经完全能体现你对“枚举优化”的理解了。滑动窗口解法可以作为进阶拓展等二分解法 AC 之后再去想怎么压常数和降复杂度。3.4 两条路的取舍建议我个人的建议是先掌握二分答案因为它的正确性容易证明代码量小也不容易在边界条件上翻车。等熟练之后再尝试用滑动窗口重新实现一遍这个转化过程本身就是很好的一维前缀和 双指针的综合练习。如果是在面试中遇到这道题建议先给暴力解法再给前缀和 二分解法。这样面试官能清楚看到你的优化思路是怎么一步步推进的。一上来就写最优解反而可能让对方觉得你是背题而不是真正理解。4. 三种写法的完整代码与逐行解读4.1 写法一暴力枚举所有正方形这种写法虽然会超时但它是理解的起点。核心就是三层循环枚举左上角的行、列再枚举边长。class Solution { public: int maxSideLength(vectorvectorint mat, int threshold) { int m mat.size(), n mat[0].size(); // 构建二维前缀和 vectorvectorlong long pre(m 1, vectorlong long(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] mat[i-1][j-1]; } } // 计算子矩阵和 auto sumRegion [](int r1, int c1, int r2, int c2) { return pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]; }; int ans 0; int maxLen min(m, n); for (int i 0; i m; i) { for (int j 0; j n; j) { for (int k 1; k maxLen; k) { if (i k m || j k n) break; if (sumRegion(i, j, i k - 1, j k - 1) threshold) { ans max(ans, k); } } } } return ans; } };这里我把 pre 的类型写成了 long long原因后面第五部分会专门讲。sumRegion 是 C 的 lambda 表达式它捕捉了 pre 数组方便在循环里反复调用。很多人第一次写子矩阵和的时候会在坐标上加加减减搞混建议在草稿纸上画一个 3x3 的矩阵手动推导一遍。4.2 写法二前缀和 二分边长这是推荐掌握的写法。用二分替代第三层循环check 函数负责判断某个边长 k 是否可行。class Solution { public: int maxSideLength(vectorvectorint mat, int threshold) { int m mat.size(), n mat[0].size(); vectorvectorlong long pre(m 1, vectorlong long(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] mat[i-1][j-1]; } } auto check [](int k) - bool { for (int i 0; i k m; i) { for (int j 0; j k n; j) { long long s pre[ik][jk] - pre[i][jk] - pre[ik][j] pre[i][j]; if (s threshold) return true; } } return false; }; int lo 0, hi min(m, n); while (lo hi) { int mid (lo hi 1) / 2; if (check(mid)) { lo mid; } else { hi mid - 1; } } return lo; } };重点说一下二分模板。这里我用了 mid (lo hi 1) / 2 这种上取整的写法原因是当 lo0, hi1 时如果 check(0) 一定返回 true那么我们希望下一次循环仍然能让 lo 往右移动避免进入死循环。如果你用了 mid (lo hi) / 2当 lo0, hi1 时会一直卡在 mid0 出不来。另外 check 里的循环边界写成 i k m等价于 i m - k。后者在语义上更直观左上角位置 i 最多只能取到 m-k否则正方形会超出矩阵下边界。4.3 写法三Python 版本刷题速度更快Python 的写法思路完全一样只是语法更简洁。在 LeetCode 上 Python 的常数会略大但二分的判断次数很少通常也能过。class Solution: def maxSideLength(self, mat: List[List[int]], threshold: int) - int: m, n len(mat), len(mat[0]) pre [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): pre[i][j] ( pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] mat[i-1][j-1] ) def ok(k: int) - bool: for i in range(m - k 1): for j in range(n - k 1): s ( pre[ik][jk] - pre[i][jk] - pre[ik][j] pre[i][j] ) if s threshold: return True return False lo, hi 0, min(m, n) while lo hi: mid (lo hi 1) // 2 if ok(mid): lo mid else: hi mid - 1 return lo我在本地测试时发现Python 版在 mn300、元素比较大的情况下运行时间大约在 200ms 左右LeetCode 上是能稳定通过的。这里的关键还是 pre 数组的构建Python 的列表推导式虽然简洁但如果你不熟悉用普通的双循环嵌套也完全没问题。4.4 代码细节提醒写完代码之后建议自己跑几个用例。最常用的两个mat [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold 4预期输出 2。mat [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold 1预期输出 0。第二个用例是用来验证 threshold 小于最小格子值的场景。如果代码返回的不是 0说明可能在二分的初始区间或者 check 函数里出现了问题。还有一点我在代码里统一用了 long long但在 check 函数里计算子矩阵和时也用了 long long。虽然大部分情况下 int 够用但一旦去看旧题目的讨论区你会发现有相当多的人因为 int 溢出而 WA。能用 long long 就用 long long这是最省心的选择。5. 常见问题排查与实测心得5.1 边界条件threshold 为 0、矩阵为空LeetCode 的题目通常默认矩阵不为空但你还是应该习惯性地判断一下。如果 m 或 n 为 0直接返回 0。threshold 为 0 的情况因为矩阵元素都是正整数所以任何边长大于等于 1 的正方形元素和都大于 0不可能满足条件。这种情况下你的二分初始区间是 [0, min(m,n)]check(0) 应该返回 true所以最终结果会正确返回 0不需要额外特判。不过有一种特殊情况你需要小心题目描述里说的是“元素和小于等于阈值”如果你的代码里比较条件写成了严格小于那 threshold 恰好等于某个正方形和的情况就会被漏掉返回的答案会偏小。这种边界错误在二分的 check 函数里特别隐蔽因为普通测试用例不一定能覆盖到。5.2 一个 bug前缀和数组搞成 int 还是 long long这是我第一次写这道题时踩过的坑。题目给出的元素值范围虽然单个不大但整个矩阵的总和可能会非常大。假设 mn300每个元素是 100000那整个矩阵的和就是 300 x 300 x 100000 90 亿远远超过 int 的最大值。如果用 int 存前缀和在计算大子矩阵和的时候就会溢出溢出之后数值变成负数check 函数就会误判导致整个二分逻辑全乱。所以我的建议是C 里前缀和数组直接用 long longPython 里 int 没有溢出问题可以放心。这个教训同样适用于其他二维前缀和题目凡是涉及求和先想一想累加会不会溢出不要等到 WA 了再回去改类型。5.3 实测对比三种写法的时间差距我在本地用了几组随机数据测试矩阵规模分别是 100x100、200x200、300x300。在 100x100 的矩阵上暴力和二分的差距还不太明显都很快。到了 200x200暴力枚举加前缀和的耗时大约是二分的 5 倍。到 300x300差距就拉开了暴力要跑两百多毫秒而二分只需要二十多毫秒。如果矩阵再大一些比如 1000x1000暴力基本就跑不动了而二分依然可以在几十毫秒内完成。这其实印证了一个观点在算法题里优化枚举维度往往比优化常数更重要。5.4 这道题可以怎么扩展刷题最忌讳的就是孤立地背一道题的解法。1292 的核心是二维前缀和 单调性二分这两个知识点可以迁移到很多其他题上。最直接的姊妹题是 304. 二维区域和检索 - 矩阵不可变它考察的是前缀和的构建和查询没有二分部分适合用来巩固基础。221. 最大正方形 则是用动态规划求全 1 正方形的最大面积和这道题的思路完全不同但对比着刷会很有意思。还有 1139. 最大的以 1 为边界的正方形它同样涉及正方形枚举但条件变成了边界为 1内部不要求解法又要换一个角度。如果你在准备面试建议把这道题和 221 放一起复习。面试官经常会先问你“怎么求最大正方形面积”然后延伸成“如果正方形内部元素和有限制怎么办”这时候你如果能从 DP 切换到前缀和 二分会是很加分的表现。我个人在实际操作中的体会是这类“矩阵 阈值 最大/最小”的题目只要看到“元素和”“子矩阵”“最大边长”这些关键词第一反应就应该是二维前缀和。先把求和问题解决掉再分析单调性考虑能不能二分最后才是考虑滑动窗口等更复杂的优化。这个套路一旦形成肌肉记忆遇到同类的题会顺畅很多。另外还有一个实战技巧第一次写这种题先别追求最优解老老实实把暴力解法和前缀和解法各写一遍然后对比它们的耗时。只有亲自感受到 O(mn·min(m,n)) 和 O(mn·log(min(m,n))) 的差距你才会真正理解为什么枚举优化这么重要。刷题不是比谁 AC 得快而是比谁能把一道题背后的原理吃透。