LeetCode 363. 矩形区域不超过 K 的最大数值和
题目描述
题意分析
在矩阵中选择一个非空连续矩形，要求其元素和不超过
k，并尽量大。矩阵元素和k都可能为负，题目保证至少存在一个合法矩形，因此答案不能默认从 $0$ 开始。
解法：短维边界枚举 + 有序前缀查询
核心思路
[!blue]
一个矩形由两条行边界和两条列边界确定。先固定上下两行
start、end，将这几行按列累加成一维数组sums，其中sums[c]就是第c列在行范围内的总和。此时sums中任意连续子数组的和，恰好对应这个行范围内一个矩形的和，二维问题就缩成了一维问题。固定
start后让end逐步扩大，每次只把新加入的一行累加到sums，不必重新计算整段。换一个start时再清零。若行数大于列数，就交换两维的角色，固定左右列、按行压缩；代码通过compressRows改变取值方向，不需要真的转置矩阵。这样把成对枚举的边界放在较短维度，尤其适合题面提出的“行数远大于列数”。接下来求一维数组中不超过
k的最大非空子数组和。扫描到当前右端时，设当前前缀和为prefix，选定左端之前的历史前缀为previous，子数组和就是prefix - previous。合法条件可改写为previous >= prefix - k；在这个条件下，previous越小，得到的和越大。因此维护一个按数值有序的历史前缀集合，每次查询不小于
prefix - k的最小值。Java 的TreeSet.ceiling直接完成这个下界查询；Go 用有序切片和二分找到第一个满足条件的位置。若不存在这样的历史前缀，说明没有以当前项为右端的合法子数组，只跳过本轮更新，继续扫描即可。初始把空前缀 $0$ 放入集合，以覆盖从第一项开始的子数组。每轮必须先查询，再插入当前前缀，确保被减去的前缀来自更早位置，排除用当前位置减自身得到的空区间。相同前缀值可以只保存一次，因为本题只比较和的大小，不需要区分产生相同和的左端位置。
Java 集合的查询和插入都是对数时间；Go 虽然查询位置用二分，插入仍要移动切片后缀，因此其复杂度更高，不能把插入也算成对数时间。负数还会使前缀值和窗口和失去单调性，所以这里不能直接用普通滑动窗口替代有序查询。
对每组边界计算一维最优值，再更新全局答案。答案初始化为最小整数，以容纳全负的合法结果；某组边界完全没有合法子数组时，它返回的最小整数不会错误提高答案。一旦找到和恰好为
k的矩形，已经达到允许的上界，可以立即结束。
解题步骤
- 选择短维度枚举起止边界。
- 固定起点后增量维护压缩数组。
- 每个压缩数组建立历史前缀，逐个查询 prefix-k 的下界。
- 更新合法最大和，达到 k 即可返回。
代码实现
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int rows = matrix.length;
int cols = matrix[0].length;
int small = Math.min(rows, cols);
int large = Math.max(rows, cols);
boolean compressRows = rows <= cols;
int answer = Integer.MIN_VALUE;
for (int start = 0; start < small; start++) {
// 每个新起点重置压缩和，终点扩展时逐层累加。
int[] sums = new int[large];
for (int end = start; end < small; end++) {
for (int i = 0; i < large; i++) {
sums[i] += compressRows ? matrix[end][i] : matrix[i][end];
}
answer = Math.max(answer, bestNoLargerThanK(sums, k));
if (answer == k) {
return k;
}
}
}
return answer;
}
private int bestNoLargerThanK(int[] nums, int k) {
TreeSet<Integer> seen = new TreeSet<>();
seen.add(0);
int prefix = 0;
int best = Integer.MIN_VALUE;
for (int value : nums) {
prefix += value;
// 历史前缀至少为当前前缀减上界，取最小合法值使区间和最大。
Integer previous = seen.ceiling(prefix - k);
if (previous != null) {
best = Math.max(best, prefix - previous);
}
// 先查询后插入当前前缀，避免用自身组成空区间。
seen.add(prefix);
}
return best;
}
}
import "sort"
func maxSumSubmatrix(matrix [][]int, k int) int {
rows, cols := len(matrix), len(matrix[0])
small, large := rows, cols
compressRows := true
if rows > cols {
small, large = cols, rows
compressRows = false
}
maxInt := int(^uint(0) >> 1)
answer := -maxInt - 1
for start := 0; start < small; start++ {
// 每个新起点重置压缩和，终点扩展时逐层累加。
sums := make([]int, large)
for end := start; end < small; end++ {
for i := 0; i < large; i++ {
if compressRows {
sums[i] += matrix[end][i]
} else {
sums[i] += matrix[i][end]
}
}
candidate := bestNoLargerThanK(sums, k)
if candidate > answer {
answer = candidate
}
if answer == k {
return k
}
}
}
return answer
}
func bestNoLargerThanK(nums []int, k int) int {
maxInt := int(^uint(0) >> 1)
best := -maxInt - 1
seen := []int{
0,
}
prefix := 0
for _, value := range nums {
prefix += value
// 历史前缀至少为当前前缀减上界，取最小合法值使区间和最大。
index := sort.SearchInts(seen, prefix-k)
if index < len(seen) && prefix-seen[index] > best {
best = prefix - seen[index]
}
// 先查询后插入当前前缀，避免用自身组成空区间。
position := sort.SearchInts(seen, prefix)
if position == len(seen) || seen[position] != prefix {
seen = append(seen, 0)
copy(seen[position+1:], seen[position:])
seen[position] = prefix
}
}
return best
}
复杂度分析
- 时间复杂度：设短边长为 s、长边长为 l，Java 为 $O(s²l\log(l+1))$，Go 因切片插入为 $O(s²l²)$。
- 空间复杂度：$O(l)$，保存压缩和及历史前缀。
关键点总结
[!green]
- 查不小于 prefix-k 的最小历史值，不是查上界以下的最大值。
- 当前前缀在查询完成后才加入，排除空子数组。
- 负数使前缀不单调，不能直接依赖普通滑窗。
易错点总结
[!yellow]
- 使用 floor 查找：差值可能超过 k。
- 漏掉初始前缀零：从第一项开始的区间无法统一计算。
- 更换起点却不重置压缩和：混入上一组边界的数据。
- 答案初始化为零：合法最优值可能为负。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.24. 最大子矩阵 | 困难 | 同样固定两条行边界压成一维数组，本题还限制和不超过k，不能只用普通Kadane。 |
| 560. 和为 K 的子数组 | 中等 | 同样把区间和改写为两前缀之差，本题需查满足范围的最优前缀，而非只查某个精确值。 |