363. 矩形区域不超过 K 的最大数值和
题目描述
输入一个 m x n 的整数矩阵 matrix 和一个整数 k。矩阵中任意由连续若干行、连续若干列围成的区域都算一个矩形，矩形的和是其中所有元素之和。
在所有矩形中，只看和不超过 k 的那些，返回其中最大的和。
题目保证至少有一个矩形的和不超过 k。
示例 1
输入：matrix = [[1,0,1],[0,-2,3]], k = 2 输出：2
解释：取右侧两列构成的矩形 [[0,1],[-2,3]]，和为 2，恰好等于 k。
示例 2
输入：matrix = [[2,2,-1]], k = 3 输出：3
解释：取前两个元素 [2,2] 得到 4 超过了 k，取 [2,2,-1] 和为 3。
数据范围
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-100 <= matrix[i][j] <= 100-10^5 <= k <= 10^5
进阶：如果行数远多于列数，应怎样调整解法？
解题思路：枚举上下边界 + 有序集合
枚举上边界 top 和下边界 bot，把这几行按列加起来，压成一维数组 col。问题变成：在 col 中找和不超过 k 的最大子数组和。子数组和 = cur - pre（两个前缀和之差），要求 cur - pre <= k，即 pre >= cur - k；为了让差尽量大，pre 要尽量小。所以把过去的前缀和放进有序列表 seen，用 bisect_left 找第一个 >= cur - k 的前缀和。
为什么正确
处理到第 c 列时，seen 是前缀和 P0=0, P1, …, Pc 的有序版本；best 是已检查过的子矩形中不超过 k 的最大和。
复杂度分析
时间 O(m² · n log n)（列表插入在 Python 里是 O(n)，可用平衡树做到 log n）；空间 O(n)。如果行比列多，可以转置后再做。
易错点
要找的是“第一个 >= cur - k”的前缀和（bisect_left），不是最接近 cur 的。seen 初始要放入 0，代表从第 0 列开始的子数组。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
m, n = len(matrix), len(matrix[0])
best = -10**9
for top in range(m):
col = [0] * n
for bot in range(top, m):
for c in range(n):
col[c] += matrix[bot][c]
seen = [0]
cur = 0
for v in col:
cur += v
i = bisect_left(seen, cur - k)
if i < len(seen):
best = max(best, cur - seen[i])
insort(seen, cur)
return bestclass Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int best = -1000000000;
for (int top = 0; top < m; top++) {
int[] col = new int[n];
for (int bot = top; bot < m; bot++) {
for (int c = 0; c < n; c++) {
col[c] += matrix[bot][c];
}
TreeSet<Integer> seen = new TreeSet<>();
seen.add(0);
int cur = 0;
for (int v : col) {
cur += v;
Integer ceil = seen.ceiling(cur - k);
if (ceil != null) {
best = Math.max(best, cur - ceil);
}
seen.add(cur);
}
}
}
return best;
}
}class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
int best = -1000000000;
for (int top = 0; top < m; top++) {
vector<int> col(n, 0);
for (int bot = top; bot < m; bot++) {
for (int c = 0; c < n; c++) {
col[c] += matrix[bot][c];
}
multiset<int> seen = {0};
int cur = 0;
for (int v : col) {
cur += v;
auto it = seen.lower_bound(cur - k);
if (it != seen.end()) {
best = max(best, cur - *it);
}
seen.insert(cur);
}
}
}
return best;
}
};func maxSumSubmatrix(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
best := -1000000000
for top := 0; top < m; top++ {
col := make([]int, n)
for bot := top; bot < m; bot++ {
for c := 0; c < n; c++ {
col[c] += matrix[bot][c]
}
seen := []int{0}
cur := 0
for _, v := range col {
cur += v
i := sort.SearchInts(seen, cur-k)
if i < len(seen) {
if cur-seen[i] > best {
best = cur - seen[i]
}
}
p := sort.SearchInts(seen, cur+1)
seen = append(seen, 0)
copy(seen[p+1:], seen[p:])
seen[p] = cur
}
}
}
return best
}var maxSumSubmatrix = function(matrix, k) {
const lb = (a, x) => { let lo = 0, hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; };
const m = matrix.length, n = matrix[0].length;
let best = -1000000000;
for (let top = 0; top < m; top++) {
const col = new Array(n).fill(0);
for (let bot = top; bot < m; bot++) {
for (let c = 0; c < n; c++) {
col[c] += matrix[bot][c];
}
const seen = [0];
let cur = 0;
for (const v of col) {
cur += v;
const i = lb(seen, cur - k);
if (i < seen.length) {
best = Math.max(best, cur - seen[i]);
}
seen.splice(lb(seen, cur + 1), 0, cur);
}
}
}
return best;
};function maxSumSubmatrix(matrix: number[][], k: number): number {
const lb = (a: number[], x: number): number => { let lo = 0, hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; };
const m = matrix.length, n = matrix[0].length;
let best = -1000000000;
for (let top = 0; top < m; top++) {
const col = new Array(n).fill(0);
for (let bot = top; bot < m; bot++) {
for (let c = 0; c < n; c++) {
col[c] += matrix[bot][c];
}
const seen = [0];
let cur = 0;
for (const v of col) {
cur += v;
const i = lb(seen, cur - k);
if (i < seen.length) {
best = Math.max(best, cur - seen[i]);
}
seen.splice(lb(seen, cur + 1), 0, cur);
}
}
}
return best;
}其他解法
暴力枚举矩形的四条边，O(m²n²)；主解法只枚举上下边，把左右边的选择变成一维「不超过 k 的最大子数组和」，用有序集合二分将一维降到 log。
解法 2：二维前缀和 + 枚举所有矩形 时间 O(m² n²)，空间 O(mn)
先求二维前缀和 pre，使任意矩形的和都能 O(1) 算出：以 (r1, c1) 为左上角、(r2, c2) 为右下角的和是 pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]。枚举所有左上角和右下角，记录不超过 k 的最大和。
思路简单，不需要有序集合。矩形个数约为 m²n²/4，在 100×100 的数据范围下约 2.5×10⁷ 次运算，编译型语言勉强可用，Python 容易超时。适合作为对拍基准。
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
m, n = len(matrix), len(matrix[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j]
best = -10**9
for r1 in range(m):
for r2 in range(r1, m):
for c1 in range(n):
for c2 in range(c1, n):
s = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1]
if best < s <= k:
best = s
return bestclass Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int[][] pre = new int[m + 1][n + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
int best = -1000000000;
for (int r1 = 0; r1 < m; r1++)
for (int r2 = r1; r2 < m; r2++)
for (int c1 = 0; c1 < n; c1++)
for (int c2 = c1; c2 < n; c2++) {
int s = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
if (s <= k && s > best) best = s;
}
return best;
}
}class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
int best = -1000000000;
for (int r1 = 0; r1 < m; r1++)
for (int r2 = r1; r2 < m; r2++)
for (int c1 = 0; c1 < n; c1++)
for (int c2 = c1; c2 < n; c2++) {
int s = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
if (s <= k && s > best) best = s;
}
return best;
}
};func maxSumSubmatrix(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
pre := make([][]int, m+1)
for i := range pre {
pre[i] = make([]int, n+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j]
}
}
best := -1000000000
for r1 := 0; r1 < m; r1++ {
for r2 := r1; r2 < m; r2++ {
for c1 := 0; c1 < n; c1++ {
for c2 := c1; c2 < n; c2++ {
s := pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]
if s <= k && s > best {
best = s
}
}
}
}
}
return best
}var maxSumSubmatrix = function(matrix, k) {
const m = matrix.length, n = matrix[0].length;
const pre = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
let best = -1e9;
for (let r1 = 0; r1 < m; r1++)
for (let r2 = r1; r2 < m; r2++)
for (let c1 = 0; c1 < n; c1++)
for (let c2 = c1; c2 < n; c2++) {
const s = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
if (s <= k && s > best) best = s;
}
return best;
};function maxSumSubmatrix(matrix: number[][], k: number): number {
const m = matrix.length, n = matrix[0].length;
const pre: number[][] = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
let best = -1e9;
for (let r1 = 0; r1 < m; r1++)
for (let r2 = r1; r2 < m; r2++)
for (let c1 = 0; c1 < n; c1++)
for (let c2 = c1; c2 < n; c2++) {
const s = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
if (s <= k && s > best) best = s;
}
return best;
}