LeetCode 363. 矩形区域不超过 K 的最大数值和

2023-04-06 HGNULB 约 8 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 363. 矩形区域不超过 K 的最大数值和

题意分析

给一个 $m \times n$ 的整数矩阵和一个整数 k，要在矩阵中找一个子矩形（由连续的若干行和连续的若干列围成），使它内部所有元素之和不超过 k 且尽可能大，返回这个和。题目保证一定存在这样的矩形。

注意目标不是「最大子矩形和」，而是「不超过 k 的前提下最大」。这个 带上界的最大化 是全题的难点所在：普通的最大子矩形和可以贪心地一路累加（Kadane 算法），但加了上界之后，局部最优不再蕴含全局最优——一段和更大的区间可能因为超过 k 而完全不可用，反而要选一段更小的。

矩阵元素可以为负，这一条很关键。它意味着前缀和序列不单调，任何依赖「和随长度单调增长」的滑动窗口或双指针都不成立。

数据规模：$m, n \le 100$，但进阶提到「如果行数远大于列数怎么办」。规模允许 $O(m^2 n \log n)$ 这个量级（约 $100^2 \times 100 \times 7 \approx 7 \times 10^6$），却不允许 $O(m^2n^2)$ 之上再套一层。而「行远大于列」的提示告诉我们：算法应当在较短的那一维上做平方枚举，必要时先转置矩阵。

边界：k 可以是负数，此时答案必然是某个负和；矩阵可能只有一行或一列；答案初值必须能被任何合法解覆盖，所以要取一个足够小的哨兵而不是 0。

解法：枚举上下边界 + 前缀和 + 有序集合

核心思路

先在较短维度上枚举两条边界，把边界之间的元素按另一维累加成一维数组 sums。这样每个子矩形都唯一对应某次边界枚举中的一个连续子数组，二维问题被完整降维。

一维子问题是：求和不超过 k 的最大连续子数组。设当前前缀和为 prefix，历史前缀为 previous，需要满足：

prefix - previous <= k，即 previous >= prefix - k。

为让差值最大，应在历史前缀中取“大于等于 prefix-k 的最小值”，也就是有序集合的 ceiling/lower_bound。集合初始放入 0，并且必须先查询、后插入当前前缀，避免选择空子数组。

不变量：扫描一维数组时，有序集合恰好包含当前下标之前的全部前缀和；sums 恰好是当前两条边界之间沿长维度的压缩和。

正确性：边界枚举覆盖所有短维区间；对固定边界，连续子数组覆盖所有长维区间。对每个右端点，ceiling(prefix-k) 给出满足上界的最优左端前缀。因此算法检查并最优处理了每个矩形。

Java 的 TreeSet 使一维查询和插入均为对数时间。Go 标准库没有有序集合，本文用有序切片与二分保持同一逻辑；插入需要线性移动，但矩阵边长不超过 100，无需引入自定义平衡树。

解题步骤

令 small=min(rows,cols)、large=max(rows,cols)，在短维度枚举起止边界。

固定起点后逐步扩展终点，并增量更新长度为 large 的压缩数组。

对每个压缩数组，从左到右累加前缀和，在历史有序前缀中查询 ceiling(prefix-k)。

用合法差值更新答案；若已经等于 k，达到理论上界，可立即返回。

[[1,0,1],[0,-2,3]]、k=2 中，固定第一行得到压缩数组 [1,0,1]，整个数组的和正好为 2，因此答案为 2。

负数反例 [-5]、k=-1 的答案是 -5，答案初值不能设为 0。查询前还必须先放入前缀 0，否则会漏掉从压缩数组首位开始的区间。

代码实现

import java.util.TreeSet;

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=\min(m,n)$、$l=\max(m,n)$。

Java 时间复杂度：$O(s^2l\log l)$；TreeSet 查询和插入均为 $O(\log l)$。

Go 时间复杂度：$O(s^2l^2)$；二分查询为 $O(\log l)$，但有序切片插入为 $O(l)$。

空间复杂度：$O(l)$，用于压缩数组和历史前缀。

关键点总结

在较短维度做平方枚举，避免矩阵长宽悬殊时浪费计算。

固定两条边界后增量维护压缩和，二维矩形转为一维连续区间。

约束变形后要查找 ceiling(prefix-k)，不是 floor。

历史前缀先放 0，并坚持先查询、后插入。

矩阵含负数，前缀和不单调，滑动窗口和普通 Kadane 均不适用。

易错点总结

用 floor 查询：可能选择过小的历史前缀，使子数组和超过 k。

忘记初始前缀 0：单格 [[2]]、k=3 会漏掉唯一矩形。

先插入当前前缀再查询：可能选中自身，产生题目不允许的空子数组和 0。

更换起始边界时不清空压缩数组：会混入上一组边界的数据。

答案初值为 0：[[-5]]、k=-1 的正确答案是 -5。

始终在行维度做平方枚举：长宽悬殊时会错过维度优化带来的数量级收益。

相似题目

题目	难度	考察点
53. 最大子数组和	中等	去掉上界后的一维子问题，Kadane 一趟即可，对照理解上界带来的额外代价
面试题 17.24. 最大子矩阵	困难	同样固定上下边界降维，但一维子问题是无上界的 Kadane，还要还原坐标
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和的标准载体，是暴力枚举四条边时把求和降到 $O(1)$ 的前置技能
327. 区间和的个数	困难	同样把条件变形成前缀和的范围查询，但求的是计数，用归并或树状数组
1074. 元素和为目标值的子矩阵数量	困难	同为固定上下边界降维，一维子问题换成哈希表统计等于目标值的前缀和
209. 长度最小的子数组	中等	元素全正因而前缀和单调，可用滑动窗口，用来对照本题为何不能用双指针
152. 乘积最大子数组	中等	负数破坏单调性后需要同时维护最大与最小两个状态，另一类应对负数的手法