LeetCode 1292. 元素和小于等于阈值的正方形的最大边长
目录
题目描述
题意分析
在一个 $m \times n$ 的矩阵里找一个正方形子矩阵，要求它的元素之和不超过
threshold，返回可能的最大边长；一个都找不到就返回 0。
有两个约束必须一起看：矩阵元素全部非负（取值范围 $[0, 10^5]$），且要找的是正方形而不是任意矩形。非负这一条是本题能用二分的唯一依据——它保证了「边长 L 可行 ⇒ 边长 L-1 也可行」，因为把一个合法正方形裁掉一圈得到的小正方形，和只会更小或相等。如果允许负数，这个单调性立刻崩塌。
规模：$m, n$ 最多 300，
threshold最多 $10^5$。$m \times n = 9 \times 10^4$，枚举所有正方形位置是 $O(mn)$；如果对每个位置再暴力求和，代价会乘上 $O(L^2)$，总量级到 $10^{10}$，不可接受。这明确指向「区域和必须能 $O(1)$ 查询」。
答案的取值范围是 $[0, \min(m, n)]$，是一段连续整数，且如上所述具有单调性——这正是二分答案的标准形态。
边界：整个矩阵所有元素都大于 threshold（答案 0）、threshold 极大（答案是 $\min(m,n)$）、矩阵只有一行或一列、和恰好等于 threshold。
解法：二维前缀和 + 二分
核心思路
先用二维前缀和把任意正方形的元素和降为 $O(1)$ 查询。定义
prefix[i][j]为原矩阵半开区域[0,i) x [0,j)的和，则：
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]右下角位于前缀坐标
(i,j)、边长为len的正方形之和为：
prefix[i][j] - prefix[i-len][j] - prefix[i][j-len] + prefix[i-len][j-len]再定义判定
exists(len)：是否存在和不超过threshold的len x len正方形。矩阵元素非负，所以若exists(len)为真，从该正方形中截取任意(len-1) x (len-1)子方形，其和不会增大，exists(len-1)也为真。可行边长因此构成从 0 开始的连续前缀，可以二分最大可行值。二分保持两个条件：
left已知可行，答案始终位于[left,right]。使用上中位数；mid可行时保留它并令left = mid，不可行时令right = mid - 1。前缀总和按题面范围可能超过 32 位，因此 Java 使用
long、Go 使用int64，避免溢出破坏判定单调性。
解题步骤
- 建立
(m+1) x (n+1)的 64 位前缀和数组；第 0 行和第 0 列作为零哨兵。- 令
left = 0、right = min(m,n)，其中 0 表示没有合法正方形。- 用上中位数检查
mid。exists(mid)枚举所有右下角位置，并用容斥公式查询区域和。- 可行时提高下界，否则降低上界；区间收敛后返回
left。样例矩阵
[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]、threshold = 4：边长 2 的左上方块和为 4，可行；所有边长 3 的方块都超过阈值，因此答案为 2。边界反例
[[100]]、threshold = 1的答案是 0，所以二分下界不能初始化为 1。若left = 2,right = 3时使用下中位数，可行分支会令left仍为 2，循环无法收敛。
代码实现
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
long[][] prefix = new long[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1]
- prefix[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int left = 0;
int right = Math.min(m, n);
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (exists(prefix, m, n, mid, threshold)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean exists(long[][] prefix, int m, int n, int len, int threshold) {
for (int i = len; i <= m; i++) {
for (int j = len; j <= n; j++) {
long total = prefix[i][j] - prefix[i - len][j]
- prefix[i][j - len] + prefix[i - len][j - len];
if (total <= threshold) {
return true;
}
}
}
return false;
}
}
func maxSideLength(mat [][]int, threshold int) int {
m := len(mat)
n := len(mat[0])
prefix := make([][]int64, m+1)
for i := 0; i <= m; i++ {
prefix[i] = make([]int64, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + int64(mat[i-1][j-1])
}
}
left, right := 0, m
if n < right {
right = n
}
for left < right {
mid := left + (right-left+1)/2
if existsSquare(prefix, m, n, mid, threshold) {
left = mid
} else {
right = mid - 1
}
}
return left
}
func existsSquare(prefix [][]int64, m, n, length, threshold int) bool {
for i := length; i <= m; i++ {
for j := length; j <= n; j++ {
total := prefix[i][j] - prefix[i-length][j] - prefix[i][j-length] + prefix[i-length][j-length]
if total <= int64(threshold) {
return true
}
}
}
return false
}
复杂度分析
- 时间复杂度：$O(mn \log \min(m,n))$。构建前缀和为 $O(mn)$；每轮判定最坏扫描全部位置。
- 空间复杂度：$O(mn)$，来自二维前缀和。
关键点总结
- 二维前缀和负责 $O(1)$ 区域求和，二分只负责减少候选边长数量。
- 二分成立的依据是元素非负；若允许负数，大边长可行不再推出小边长可行。
- 最大可行值模板要配套使用上中位数、
left = mid和right = mid - 1。- 0 是天然的可行哨兵，覆盖“没有任何合法正方形”的返回值。
- 区域总和先估算上界，本题实现使用 64 位存储。
易错点总结
- 使用下中位数：
left = 2,right = 3且 2 可行时区间不缩小，会死循环。left从 1 开始：[[100]]、threshold = 1会错误返回 1，而正确答案是 0。- 前缀和容斥漏减或漏加重叠区域：非左上角方块会得到错误甚至负的和。
- 判定循环不是从
len开始，或上界写成< m、< n：会越界或漏掉最后一行、列的候选。right取max(m,n)：会搜索不可能存在的正方形边长。- 用 32 位前缀和：按题面上界总和可达 $9 \times 10^9$，溢出后可能把大方块误判为可行。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 只考前缀和的构建与查询，是本题去掉二分后的裸模板 |
| 1314. 矩阵区域和 | 中等 | 查询区域随中心点移动且要裁剪到边界，重点是下标夹取 |
| 221. 最大正方形 | 中等 | 元素是 0/1，改用 dp[i][j] 递推边长，无需前缀和 |
| 363. 矩形区域不超过 K 的最大数值和 | 困难 | 元素可为负导致单调性失效，需枚举行区间加有序集合查找 |