刷过LeetCode 1292这道题的朋友应该都有印象第一次看到“元素和小于等于阈值的正方形最大边长”时我第一反应是直接暴力枚举所有正方形然后把每个正方形内的元素加起来比较。结果可想而知提交之后超时得明明白白。后来认真做了一遍发现这道题的核心其实就是两件事二维前缀和怎么建以及怎么把“枚举所有正方形”这个过程优化到能让人接受。今天这篇就把这道题的思路拆开揉碎聊一聊顺便把我自己踩过的坑和用下来的心得都写出来希望能帮到正在跟矩阵类题目缠斗的人。这道题属于典型的前缀和结合枚举优化的中等题数据范围是m、n最大300threshold最大10^9矩阵元素都是非负整数。这些条件决定了我们不能用O(m^3 n^3)的暴力更不能在每次求和时都临时累加。适合参考的人包括刚开始刷LeetCode热题100但卡在二维数组题目的新手准备面试想巩固基础算法的同学以及想搞懂二维前缀和本质、以后遇到类似“子矩阵和”问题能直接套思路的进阶玩家。读完这篇起码你能弄明白两件事一是二维前缀和的推导过程为什么是那样二是为什么这道题用二分答案比纯线性枚举更稳以及在什么情况下可以直接枚举。1. 题目到底在问什么先拆清楚题意力扣1292的原题描述不长但里面藏着不少信息。给你一个 m x n 的矩阵 mat 和一个整数 threshold矩阵里每个元素都是正整数题目说是非负整数实际用例基本是正数。你要找到一个最大的边长 k使得矩阵中存在一个边长为 k 的正方形并且这个正方形内所有数字的和不超过 threshold。如果不存在这样的正方形返回 0。这句话里最关键的两个限定是“正方形”和“最大边长”。正方形意味着边长在行和列方向上是相等的子矩阵的行数等于列数。最大边长意味着我们不是随便找一个满足条件的就行而是要尽量大。由于矩阵的长宽可能不一样所以 k 的最大值不可能超过 min(m, n)这个上限后面会用上。再一个容易被忽略的细节是正方形的位置是任意的不一定从左上角开始。比如 matrix [[1,1,1],[1,0,1],[1,1,1]]threshold 2你可能会想找边长为2的但所有2x2子矩阵的和最小也是2那可能行。但如果不认真枚举每一个可能的左上角就很容易漏掉某个角落。之前我刷的时候就犯过这个错觉得只要把整个矩阵的平均值算一下就行结果答非所问。题目考的就是“任意位置”所以前缀和的作用就是让我们能O(1)地求出任何位置的正方形和只要枚举左上角即可。题目最后的返回值是边长而不是正方形本身。如果没有任何一个1x1的格子满足条件即单个元素都大于threshold那返回0。注意即使矩阵非空也可能返回0因为threshold可能比所有元素都小。这一点边界处理时要注意。理解到这里这道题其实已经清晰了我们需要快速求出任意正方形的元素和。那么快速求和的工具就是二维前缀和。就算没听说过它的名字也应该能意识到如果每次都用两个循环累加那就彻底掉进暴力陷阱了。2. 前缀和二维数组求和的好帮手2.1 一维前缀和回顾在写二维之前先简单回忆下一维前缀和。假设有一个数组 a长度为 n。我们提前计算一个数组 prepre[i] 表示 a[0] 到 a[i-1] 的和或者 a[1] 到 a[i]取决于你的习惯。这样当你想求 a[l] 到 a[r] 的和时不需要遍历直接 pre[r1] - pre[l] 就行。时间复杂度从O(r-l1)降到O(1)。一维前缀和的思想是“预处理快速查询”把求和的成本摊到建前缀和的那一次遍历上。二维前缀和完全一样只是多了一个维度。2.2 二维前缀和推导二维前缀和的定义设 sum[i][j] 表示从矩阵左上角 (0,0) 到 (i-1,j-1) 这个子矩阵内所有元素的和即前 i 行前 j 列的总和。这里的 i 和 j 是从0开始的但为了下标方便通常我们会把 sum 开成 (m1) x (n1)留一行一列作为0避免处理边界条件。这个技巧在二维数组题里几乎是标配一定要养成习惯。怎么计算 sum[i][j] 呢画个图特别清晰。要求的是涂色区域的总和它可以拆成三部分上面一部分是 sum[i-1][j]左边一部分是 sum[i][j-1]但是这两部分重叠了左上角那块 sum[i-1][j-1]所以加的时候要减掉一次最后再加上当前元素 mat[i-1][j-1]。公式就是sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] mat[i-1][j-1]用生活化的例子来理解想象你面前有一个格子布sum[i][j] 是整个布的面积。sum[i-1][j] 是去掉最下面一行后的面积sum[i][j-1] 是去掉最右边一列后的面积。你把这两块面积加起来时左上角的 (i-1)x(j-1) 那块被算了两次所以减掉一次。然后再加上右下角那个格子的面积就得到了整块布的面积。多算几遍这个公式形成肌肉记忆二维前缀和基本就稳了。有了 sum 之后怎么求任意一个矩形区域 (r1,c1) 到 (r2,c2) 的和所有索引都是从0开始r1r2c1c2。这个区域的和可以表示为region sum[r21][c21] - sum[r1][c21] - sum[r21][c1] sum[r1][c1]依然是容斥原理。先取包含整个区域的大矩形减去上方、左方多出来的部分再加上左上角被重复减掉的小矩形。用前缀和数组来写下标一定要注意。写习惯了之后我一般会单独封装一个函数 getSum(r1,c1,r2,c2)避免每次手写都出错。二维前缀和的构建时间复杂度是O(m*n)之后每次查询任意矩形的和都是O(1)这是整个算法能优化下去的原因。矩阵最大是300x300构建前缀和的花费9万完全没问题。3. 枚举优化思路从暴力到高效3.1 暴力做法为什么慢好现在我们来对比一下不同做法的复杂度。最暴力的方法枚举所有可能的边长 k从1到min(m,n)。对于每个 k枚举所有左上角位置再用两层循环把 k*k 个字累加起来。那么总复杂度是 O(min(m,n) * m * n * k^2)严格说是 O(m * n * min(m,n)^3) 也不为过因为 k 最大到 min(m,n)累加又是k^2。对于300x300这种数据差不多要算到 300^5 24.3亿实际略低一些但绝对是天文数字超时没有任何悬念。就算我们做一点改进先求一维前缀和然后在一个方向累加复杂度也只是降到一个平方量级的枚举加平方量级的求和依然不行。所以要真正提速核心就是两条路一是用二维前缀和把求和变成O(1)二是想办法减少枚举边长和左上角的次数。3.2 二分答案还是直接枚举有了O(1)的子矩阵求和剩下的问题变成了怎么找最大边长。最直接的方式是从大到小枚举边长 k从 min(m,n) 开始每次检查是否存在某个左上角使得正方形和 threshold如果存在就返回 k。由于 m 和 n 最大300边长的上下界范围只有300所以直接枚举边长其实也是可行的。对每个 k要枚举所有左上角位置左上角数量是 (m-k1)*(n-k1)再加上二分的引入可以进一步优化。那么问题来了直接枚举边长需要遍历每个可能的 k最多300个每个 k 要遍历左上角总次数约 sum_{k1}^{300} (301-k)^2这个量级是300^32700万对于现代OJ来说其实是可过的。但更常见、更稳妥的解法是二分答案。二分的依据是如果边长为 x 的正方形存在一个满足条件的那么边长小于 x 的正方形也一定存在。这个性质依赖于“元素和都是非负的”。因为你可以从那个满足条件的 x 边正方形里任意切出一个小正方形比如左上角不变边长缩小矩阵和只会变小或不变所以仍然 threshold。有了单调性就能用二分法查找最大边长。不过这里要小心一点如果矩阵元素含有负数单调性就会被打破边长更大的正方形和反而可能小于更小的。但题目明确说了元素都是非负所以这个规律成立。这也是很多题解里一开始就默认“可以用二分”的根本原因。所以最终的优化思路就是先用二维前缀和预处理然后对 k 进行二分查找。检查 mid 是否可行时枚举该边长下的所有左上角每次通过前缀和O(1)计算正方形和只要有一个满足条件就返回 true。二分查找的复杂度是 O(log(min(m,n)) * m * n)因为每次检查要遍历全部左上角。m*n最大9万log300不到9总共不到81万次操作非常轻松。可能有人会问既然直接枚举边长也才2700万次为什么还要二分因为二分的时间复杂度更优而且在更极端的数据范围比如mn1000下直接枚举边长会到1e9级别二分到1e7级别差距明显。虽然本题范围300直接枚举也能过但从解题思路的角度二分更值得学习。在实际面试中能说出二分前缀和的方案显然比直接枚举更有说服力。4. 完整实现与代码对照4.1 Java写法我用Java实现的时候喜欢把前缀和数组开成 (m1) x (n1)这样计算区域和时不用判断边界。判断某个边长 mid 是否可行的函数我会单独写出来保持主流程清爽。class Solution { public int maxSideLength(int[][] mat, int threshold) { int m mat.length, n mat[0].length; // 二维前缀和sum[i][j] 表示 mat[0..i-1][0..j-1] 的和 int[][] sum new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] mat[i - 1][j - 1]; } } // 二分查找最大边长 int l 0, r Math.min(m, n); while (l r) { // 注意是上取整避免死循环 int mid (l r 1) 1; if (exists(mat, sum, mid, threshold)) { l mid; } else { r mid - 1; } } return l; } private boolean exists(int[][] mat, int[][] sum, int len, int threshold) { int m mat.length, n mat[0].length; // 左上角行 i列 j取值范围要保证 ilen m, jlen n for (int i 0; i len m; i) { for (int j 0; j len n; j) { int r1 i, c1 j, r2 i len - 1, c2 j len - 1; long total sum[r2 1][c2 1] - sum[r1][c2 1] - sum[r2 1][c1] sum[r1][c1]; if (total threshold) { return true; } } } return false; } }这里面有两个细节值得说。第一是二分的中值计算用(l r 1) 1也就是向上取整。因为我们是往右缩进区间l mid如果用向下取整(lr)/2当 l1, r2 时 mid1如果 exists(1) 为 truel1r2 不变就会死循环。上取整后 mid2可以正常结束。第二是计算 total 时我特意用了 long 类型。虽然 threshold 最大是10^9但矩阵元素之和可能超过 int 范围比如300x300矩阵每个元素都是10^9的话总和是9e13远超 int 上限。在检查和之前虽然我们可以提前判断 total threshold 就退出但计算过程中已经溢出了。这就是一个很隐蔽的坑后面问题排查部分我会细说。4.2 Python写法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(length: int) - bool: for i in range(m - length 1): for j in range(n - length 1): total pre[ilength][jlength] - pre[i][jlength] - pre[ilength][j] pre[i][j] if total 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这里计算 total 时有个小技巧我直接改用 ilength 和 jlength 作为前缀和下标的边界等价于 r1i, c1j, r2ilength-1, c2jlength-1。这种写法看着更清爽不容易忘记减1。注意 Python 里 while 循环条件lo hi和上取整(lo hi 1) // 2和 Java 语义完全一致。4.3 一份可以直接抄作业的完整性对照为了方便不同语言习惯的读者我把两种写法的主要差异整理成一个简单的参考表。注意这不是代码对比而是思路在不同语言里的映射关系语言前缀和构建方式计算区域和的公式二分写法Javaint[][] sum多一行一列sum[r21][c21] - sum[r1][c21] - sum[r21][c1] sum[r1][c1](lr1)1更新 lmid rmid-1Pythonlist of list多一行一列pre[ilen][jlen] - pre[i][jlen] - pre[ilen][j] pre[i][j](lohi1)//2更新 lomid himid-1如果你习惯 C结构也差不多注意用 vectorvector 或二维 vectorlong long 类型做和。核心代码逻辑完全通用。5. 常见问题与排查技巧实录5.1 前缀和下标总是搞混这是新手最容易犯的错。我一开始写二维前缀和时也老是在减1还是不减1之间晕头转向。后来我给自己定了一个铁律前缀和数组的大小是 (m1) x (n1)下标 i 和 j 表示的是原矩阵前 i 行前 j 列。因此求以 (r1,c1) 为左上角、以 (r2,c2) 为右下角的矩形和时一定是用 sum[r21][c21] - sum[r1][c21] - sum[r21][c1] sum[r1][c1]。这里的 1 就是因为前缀和下标是从1开始处理的。如果你觉得记忆负担重可以在构建前缀和时故意把辅助数组命名为pre并且写的时候始终想着“pre[i][j] 左上角到 (i-1,j-1) 的和”。每次写完代码后用一个 2x2 的小矩阵手动推一遍比如 mat [[1,2],[3,4]]threshold10验证一下 sum 数组值和自己手算的一致。这个习惯能帮你省下大把调 bug 的时间。5.2 整数溢出问题接上面说的Java 里 int 最大约21亿。如果矩阵元素比较大比如每个元素是10^9边长300时整块矩阵和是9e13远超过 int。如果你在 Java 代码里用 int 算 total即使后面判断 threshold 返回 false计算过程中的溢出也可能导致结果异常。比如溢出后变成一个负数然后负数 thresholdthreshold 是非负数会误判为满足条件答案就会错。解决办法很直接用 long 类型保存前缀和或者至少保存 total。在 C 中用 long longPython 不需要担心溢出。Java 中如果 memory 许可直接把前缀和数组声明为 long[][]这是最省心的。不过本题数据 mn300long 数组也才3003008720KB非常小无压力。我在第一次写 Java 时偷懒用了 int结果提交通过率低了一半最后检查了半天才发现是溢出的问题这种教训希望你们不要重复。5.3 二分边界死循环二分写法里死循环是常见的坑。我比较推荐标准的上取整模板mid (l r 1) 1。这个模板对应的更新逻辑是如果 ok(mid) 为 true说明答案至少是 mid所以 l mid否则说明答案小于 midr mid - 1。循环条件是 l r结束之后 l 就指向最大可行边长。如果你用的是向下取整的模板并且 l 从0开始、r从 min(m,n) 开始可能会遇到 lmid 更新导致的死循环。举个例子l1, r2如果 ok(1) 为 true向下取整 mid1然后 l1r2 还是2循环出不去。解决方式就是上面说的上取整模板。记住这个规律以后所有“查找右边界”类的二分题都能套。5.4 检查函数中的循环范围是否正确exists 函数里左上角的行 i 必须满足 ilen m也就是 i m-len。如果不小心写成 i m当 len0 时尝试访问越界下标可能导致数组越界异常。同样的列也要保证。这是一个很基础的边界检查但越简单越容易错。我在写代码时为了省事有时候会把检查函数直接写在主类里结果一不留神循环条件就写反。提醒自己i len m这个条件别漏。5.5 返回0的边界情况如果 threshold 非常小比如0而矩阵里有元素为正那么所有边长1的正方形可能都不满足答案就是0。我们初始化 l0rmin(m,n)就算二分从未进入 ok(1) 为真的状态l 也会保持在0返回0这符合题意。但要注意如果所有元素都是0那么答案自然是 min(m,n)二分能正确找到。我们写的 ok(0) 不会被调用因为 mid 一定至少是1所以不用担心零边长问题。5.6 什么时候可以选择直接枚举边长而不是二分前面提到本题如果 mn300从大到小枚举边长每层枚举左上角总操作量大约是 300^3/6 约450万我之前粗算是2700万其实更精确是 sum_{k1}^{300} (301-k)^2 300301601/6 约904万。这个量级在 Java 上也能跑过Python 可能稍慢但也能通过。所以如果实在不熟悉二分直接枚举边长 前缀和组合也可以作为备选。不推荐的理由主要是代码多了一个外层循环而且如果数据范围变大就崩了。但理解了这个思路后你会发现二分只是一个优化手段核心依然是前缀和。遇到这类题不要只背模板先想明白“为什么可以优化”比“怎么写”更重要。6. 再聊聊这道题的价值它背后的通用思想刷题的人总喜欢把题目分成“套路题”和“思维题”。LeetCode 1292 是一道很标准的套路题但套路得很有代表性。二维前缀和本质上是在解决一类“静态区间和查询”的问题只要你有一个矩阵需要频繁查询任意子矩阵的和都应该首先考虑这个工具。除了本题还有“二维区域和检索 - 矩阵不可变”这类经典题也用同样的数据结构。另外枚举优化的思路也值得拿出来反复品味。我们首先要做的是把内部计算成本降下来得到 O(1) 的查询其次是利用单调性对答案进行二分查找。这种“预处理 单调性 二分”的组合拳在算法题里出现频率极高。比如寻找满足条件的最大/最小窗口、最长子数组等问题思路都大同小异。如果你是在准备面试可能还要注意一下空间复杂度。二维前缀和的空间是 O(m*n)完全可以接受。但如果矩阵特别大内存紧张也有滚动数组的替代方案不过那会牺牲查询速度对于本题规模完全没必要。建议先把标准方案弄透再去琢磨那些进阶玩法。写到这里我把这道题从题意、前缀和原理、优化思路到代码实现和踩坑经验全部过了一遍。最后再分享一个小技巧遇到这种带“最大边长”的矩阵题先别看题解自己用 2x2 或 3x3 的小矩阵手算一遍把推导公式写在纸上。这个方法帮我少走了很多弯路。等你亲手画出了前缀和的容斥关系再回头写代码错误率会直线下降。希望这篇能让你在遇到二维前缀和相关题目时心里更有底。