题目描述
思路解析动画文字版
记住两招:二维前缀和把矩形求和压到 O(1);边长可行性单调,于是二分边长。可行往大找,不可行往小缩。
总览 · 原始 3×4 矩阵：这是一张 3 行 4 列的矩阵,行号 0 到 2、列号 0 到 3。我们要在它里面框一个正方形,使框住的数字之和不超过 8,并且边长尽量大。第一步不是急着去框,而是先把下面这张前缀和表建出来,它能让后面任何一次正方形求和都只花常数时间。
建前缀表 · 先补一圈哨兵 0：前缀和表 s 故意比原矩阵大一圈,行列各多出一个 0 号。多出来的第 0 行、第 0 列全部填 0,叫哨兵。有了这圈 0,内部每一格都能统一用「上邻加左邻减左上邻再加本格」这一条公式来算,不用为最上行、最左列单独写边界判断。下面从 i 等于 1、j 等于 1 开始,一行一行把内部填满。
建前缀表 · 第 (1,1) 格：算 s[1][1]:它代表从矩阵左上角一直到原矩阵第 0 行第 0 列(值是 4)这块矩形的总和。正上方那块是 0,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 4,得到 4。
建前缀表 · 第 (1,2) 格：算 s[1][2]:它代表从矩阵左上角一直到原矩阵第 0 行第 1 列(值是 3)这块矩形的总和。正上方那块是 0,正左方那块是 4,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 3,得到 7。
建前缀表 · 第 (1,3) 格：算 s[1][3]:它代表从矩阵左上角一直到原矩阵第 0 行第 2 列(值是 1)这块矩形的总和。正上方那块是 0,正左方那块是 7,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 8。
建前缀表 · 第 (1,4) 格：算 s[1][4]:它代表从矩阵左上角一直到原矩阵第 0 行第 3 列(值是 1)这块矩形的总和。正上方那块是 0,正左方那块是 8,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 9。
建前缀表 · 第 (2,1) 格：算 s[2][1]:它代表从矩阵左上角一直到原矩阵第 1 行第 0 列(值是 2)这块矩形的总和。正上方那块是 4,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 2,得到 6。
建前缀表 · 第 (2,2) 格：算 s[2][2]:它代表从矩阵左上角一直到原矩阵第 1 行第 1 列(值是 4)这块矩形的总和。正上方那块是 7,正左方那块是 6,这两块把左上角那一小块 4 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 4,得到 13。
建前缀表 · 第 (2,3) 格：算 s[2][3]:它代表从矩阵左上角一直到原矩阵第 1 行第 2 列(值是 1)这块矩形的总和。正上方那块是 8,正左方那块是 13,这两块把左上角那一小块 7 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 15。
建前缀表 · 第 (2,4) 格：算 s[2][4]:它代表从矩阵左上角一直到原矩阵第 1 行第 3 列(值是 1)这块矩形的总和。正上方那块是 9,正左方那块是 15,这两块把左上角那一小块 8 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 17。
建前缀表 · 第 (3,1) 格：算 s[3][1]:它代表从矩阵左上角一直到原矩阵第 2 行第 0 列(值是 3)这块矩形的总和。正上方那块是 6,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 3,得到 9。
建前缀表 · 第 (3,2) 格：算 s[3][2]:它代表从矩阵左上角一直到原矩阵第 2 行第 1 列(值是 1)这块矩形的总和。正上方那块是 13,正左方那块是 9,这两块把左上角那一小块 6 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 17。
建前缀表 · 第 (3,3) 格：算 s[3][3]:它代表从矩阵左上角一直到原矩阵第 2 行第 2 列(值是 2)这块矩形的总和。正上方那块是 15,正左方那块是 17,这两块把左上角那一小块 13 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 2,得到 21。
建前缀表 · 第 (3,4) 格：算 s[3][4]:它代表从矩阵左上角一直到原矩阵第 2 行第 3 列(值是 1)这块矩形的总和。正上方那块是 17,正左方那块是 21,这两块把左上角那一小块 15 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 24。
前缀表建完 · 下面二分边长：十二个内部格全部填好。现在这张表里,s[i][j] 就是「从矩阵左上角到 (i-1,j-1) 」那块矩形的总和。接下来不再碰原始数字,所有正方形求和都靠这张表的四个角加加减减。边长该取多大?用二分:行列里小的那个是 3,所以边长在 0 到 3 之间,我们二分着试。
二分边长 · 区间 [0,3] 取 mid=2：二分开始。左端 l 是 0,右端 r 是行列较小值 3。取中点 mid,这里用 (l 加 r 加 1) 右移一位,等于 2;加 1 是让中点往上取整,后面 l 会跳到 mid,不补这个 1 会死循环。现在就去检查:边长 2 的正方形,能不能找到一个和 ≤ 8 的。
check(2) · 左上角 (0,0)：检查边长 2,从最靠左上的位置 (0,0) 开始。它的正方形和用四个角算:右下角 s[2][2] 是 13,减掉右上角 s[0][2] 和左下角 s[2][0],再把被减了两次的左上角 s[0][0] 加回来,得到 13。这个值大于 8,这个位置框不下,换右边一个位置。
check(2) · 左上角 (0,1)：左上角右移到 (0,1)。同样用四个角:15 减 0 减 6 加 0,等于 9。还是大于 8,继续往右挪。注意四个角的下标都跟着左上角一起平移,这就是 O(1) 的好处,挪一格不用重新加里面的数。
check(2) · 左上角 (0,2) · 命中：再往右到 (0,2)。四个角:17 减 0 减 13 加 0,等于 4。这回 4 不超过 8,找到了一个合格的边长 2 正方形。只要有一个合格就够了,立刻收手:边长 2 可行。
二分推进 · l=2, 区间 [2,3] 取 mid=3：边长 2 行得通,说明答案至少是 2,我们贪心地想要更大,把左端 l 抬到 2。新区间是 2 到 3,中点 (2 加 3 加 1) 右移一位等于 3。接着去试边长 3 能不能也找到一个和 ≤ 8 的正方形。
check(3) · 左上角 (0,0)：检查边长 3,3 行 4 列里能放下 3×3 的左上角只有两个。先看 (0,0):右下角 s[3][3] 是 21,减右上 0、减左下 0、加回左上 0,得 21。远大于 8,框不下。
check(3) · 左上角 (0,1) · 全部失败：挪到 (0,1):24 减 0 减 9 加 0,等于 15,还是大于 8。两个位置都失败,边长 3 找不到合格正方形,不可行。
二分收束 · l == r == 2：边长 3 不可行,把右端 r 压到 2。现在 l 和 r 都等于 2,区间只剩一个值,二分结束。整个过程里能成立的最大边长就是 2,这就是答案。注意题目要的是边长本身,返回 2,不是面积 4。
答案 · 边长 2 的正方形(和 4 ≤ 8)：把答案放回原矩阵看:就是右上角这个 2×2 区块,左上角在行 0 列 2,盖住行 0 到 1、列 2 到 3,四个数都是 1,加起来 4,不超过 8。它的边长是 2。边长 3 试过框不下,边长 2 框得下,所以最大边长就是 2。
边界都能手验:全比阈值大返回 0;含 0 元素且阈值 0 时单格也能成边长 1;单格 ≤ 阈值返回 1。
面试三连:前缀和建表与查询两条容斥公式;二分与滑动枚举两种解的复杂度;中点 +1 向上取整防死循环。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxSideLength(self, mat: List[List[int]], threshold: int) -> int: def check(k: int) -> bool: for i in range(m - k + 1): for j in range(n - k + 1): v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] if v <= threshold: return True return False m, n = len(mat), len(mat[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(mat, 1): for j, x in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x l, r = 0, min(m, n) while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l复杂度
- 时间：O(m·n·log(min(m,n)))，建前缀表 O(m·n)。二分边长共 O(log(min(m,n))) 次,每次 check 要扫 O(m·n) 个左上角,每个左上角靠前缀表 O(1) 求和。注:也有不二分、直接对每个左上角递增边长的 O(m·n·min(m,n)) 写法,本解走二分更快
- 空间：O(m·n)，按峰值算:前缀和表 s 是 (m+1)×(n+1),和矩阵同量级。没有递归,不额外吃栈
易错点
面试追问把动画讲成自己的话
追问二维前缀和的递推和查询公式分别是什么?
追问不二分行不行?复杂度差多少?
追问中点为什么写 (l 加 r 加 1) 右移一位、而不是 (l 加 r) 右移一位?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
子数组和排序后的区间和
LeetCode 1508 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题