LeetCode 1292. 元素和小于等于阈值的正方形的最大边长
题目描述
题意分析
在矩阵中选择一个连续的、边与矩阵行列平行的正方形区域，使其中全部元素之和不超过阈值，返回最大边长。返回的不是面积，也不是该区域的元素和。
矩阵元素均为非负数，阈值允许为零。若连边长一的格子都没有合法选择，返回零；只需存在一个合格位置，不要求所有同边长正方形都合格。
解法：二维前缀和 + 二分
核心思路
[!blue]
需要反复比较不同位置、不同边长的区域和，先用二维前缀和消除重复累加。定义
prefix[i][j]为前i行、前j列的总和，额外的零行和零列用于统一处理贴边区域。以
(i, j)为不包含的右下边界、边长为len的方块，覆盖行[i-len, i)和列[j-len, j)。从大前缀中减掉上方和左方，两块重叠部分被重复减去一次，所以再加回来，得到prefix[i][j] - prefix[i-len][j] - prefix[i][j-len] + prefix[i-len][j-len]。再定义
exists(len)为是否有某个该边长方块的和不超过阈值。若一个大方块合法，从它内部裁出更小方块，只会去掉非负数，和不会增加，所以所有更小边长也可行。可行边长构成从零开始的连续范围，可以二分寻找最大值。每次判定枚举当前边长的所有右下边界，用前缀表常数时间求和；找到一个合格方块就返回可行，全部位置都超限才不可行。可行时保留
mid并向更大边长搜索，不可行时排除mid及更大值。使用上中点配合left = mid，保证只剩两个候选时也能收缩。
解题步骤
- 构造
(m + 1) × (n + 1)的 64 位前缀和，零行、零列保留为零。- 将边长候选范围设为
[0, min(m, n)]，零表示没有合法正方形时的结果。- 取上中点，对该边长枚举从
len到矩阵边界的所有右下坐标，检查四项容斥和是否达标。- 存在合法位置则令
left = mid，否则令right = mid - 1。- 两界相遇后返回最大可行边长。
代码实现
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
// 前缀坐标表示前 i 行、前 j 列，多出零行零列。
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++) {
// 以当前前缀坐标为右下边界，容斥取边长为 len 的方块。
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])
// 前缀坐标表示前 i 行、前 j 列，多出零行零列。
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)+1))$，前缀表构造为 $O(mn)$，每轮判定最多扫描 $mn$ 个位置，二分轮数为对数级。
- 空间复杂度：$O(mn)$，保存二维前缀表；搜索只需常数个变量。
关键点总结
[!green]
- 前缀坐标表示行列数量，右下边界不包含在区域内，统一求和公式。
- 非负元素保证合法大方块包含合法小方块，从而得到边长的单调性。
- 判定是寻找任意一个合格位置，成功可提前停止，失败必须排查全部位置。
- 最大可行值二分保留左侧可行中点，需要上中点避免停滞。
易错点总结
[!yellow]
- 忘记加回上方与左方重叠区域，非贴边方块的和会被多减一次。
- 将前缀坐标与原矩阵下标混用，导致区域边界错一行或一列。
- 只检查左上角一个方块就判断该边长不可行，遗漏其他位置的合法区域。
- 下界从一开始，无法返回不存在合法方块时的零。
- 用下中点却执行
left = mid，两个候选时可能无法继续移动。- 在允许负数的矩阵上照搬相同单调性证明，裁掉负数后区域和可能增加，当前判定不再成立。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 二维前缀和提供每个正方形的常数时间区域和查询，再利用非负值对边长的单调性搜索。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！