给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
示例 1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2 输出：2 解释：蓝色边框圈出来的矩形区域[[0, 1], [-2, 3]]的数值和是2，且 2 是不超过 k 的最大数字（k = 2）。
示例 2：
输入：matrix = [[2,2,-1]], k = 3 输出：3
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-100 <= matrix[i][j] <= 100-10^5 <= k <= 10^5
进阶：如果行数远大于列数，该如何设计解决方案？
解法：前缀和 + 有序集合（TreeSet）
我们枚举矩形的上下边界，并计算出该边界内每列的元素和，则原问题转换成了如下一维问题： 给定一个整数数组和一个整数 k，计算该数组的最大区间和，要求区间和不超过 k。
题目分析
这个问题实际上是一个二维数组的最大子矩阵和问题，但是与传统的最大子矩阵和问题不同，这里增加了一个额外的条件：子矩阵的和不能超过一个给定的数值k。我们的目标是找到一个最大的子矩阵，其元素之和不超过k。
算法思路
- 枚举矩形的上下边界：我们可以固定矩形的上边界，然后枚举下边界。这样，对于每一对边界，我们可以得到一个确定的矩形区域。
- 计算列的元素和：对于每一个确定的矩形区域，我们可以计算出每列的元素和。
- 转换为一维问题：将二维问题转换为一维问题，即在每列的元素和数组中找到一个区间，使得区间和不超过
k。 - 使用有序集合优化搜索：利用有序集合（如TreeSet）来优化在列元素和数组中搜索满足条件的区间的过程。
详细步骤
- 初始化：初始化答案
ans为最小整数，用于记录不超过k的最大数值和。 - 外层循环：枚举矩形的上边界
i。 - 计算列元素和：对于每一对边界
(i, j)，计算从i到j的每一列的元素和，存储在数组sum中。 - 初始化有序集合：创建一个有序集合
set，用于存储累积和，并初始化其为包含0的集合。 - 计算累积和并更新答案：遍历
sum数组，维护当前累积和s，并使用有序集合找到最近的一个累积和，使得累加和减去这个值小于等于k。如果找到，更新答案ans。 - 添加累积和到有序集合：将当前累积和
s添加到有序集合中。 - 返回答案：返回不超过
k的最大数值和。
代码实现
Java版：
TreeSet 提供了 ceiling 和 floor 方法，用于寻找最接近指定元素的元素。ceiling 方法返回大于等于指定元素的最小元素，而 floor 方法返回小于等于指定元素的最大元素。
TreeSet<Integer> numbers = new TreeSet<>(Arrays.asList(1, 3, 6, 8, 10));
int closestGreaterOrEqual = numbers.ceiling(5); // 返回 6
int closestLessOrEqual = numbers.floor(5); // 返回 3
对于包装类Integer，我们可以使用==运算符来判断其值是否为null。
对于基本数据类型int，我们也可以使用Integer类的静态方法valueOf()来将其转换为包装类Integer，然后使用==运算符来判断其值是否为null
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int ans = Integer.MIN_VALUE;
// 枚举上边界
for (int i = 0; i < m; i++) {
int[] sum = new int[n];
// 枚举下边界
for (int j = i; j < m; j++) {
for (int c = 0; c < n; c++) {
// 更新每列的元素前缀和
sum[c] += matrix[j][c];
}
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
int s = 0;
for (int v: sum) {
s += v;
Integer ceil = set.ceiling(s - k);
if (ceil != null) {
ans = Math.max(ans, s - ceil);
}
set.add(s);
}
}
}
return ans;
}
}Python3版：
python中一个专门提供排序的库 sortedcontainers。该库提供了三个有用的类：SortedList、SortedDict、SortedSet。
官网： Sorted List — Sorted Containers 2.4.0 documentation (grantjenks.com)
from sortedcontainers import SortedList
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
m = len(matrix)
n = len(matrix[0])
ans = -inf
# 枚举上边界
for i in range(m):
colsum = [0] * n
# 枚举下边界
for j in range(i, m):
for c in range(n):
# 更新每列的元素累加和
colsum[c] += matrix[j][c]
sumset = SortedList([0])
s = 0
for v in colsum:
s += v
l = sumset.bisect_left(s - k)
if l != len(sumset):
ans = max(ans, s - sumset[l])
sumset.add(s)
return ans
复杂度分析
-
时间复杂度：O(m^2 * n * logn)。其中 m 和 n 分别是矩阵 matrix 的行数和列数。
-
空间复杂度：O(n)。