JAVA学习-练习试用Java实现“矩形区域不超过 K 的最大数值和 Ⅲ”
问题：
给定一个 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.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105
解答思路：
以下是使用 Java 实现的解决方案：
import java.util.TreeSet;public class MaxSumSubmatrix {public int maxSumSubmatrix(int[][] matrix, int k) {int rows = matrix.length;int cols = matrix[0].length;int maxSum = Integer.MIN_VALUE;for (int left = 0; left < cols; left++) {int[] rowSums = new int[rows];for (int right = left; right < cols; right++) {for (int row = 0; row < rows; row++) {rowSums[row] += matrix[row][right];}TreeSet<Integer> set = new TreeSet<>();set.add(0);int runningSum = 0;for (int sum : rowSums) {runningSum += sum;Integer ceiling = set.ceiling(runningSum - k);if (ceiling!= null) {maxSum = Math.max(maxSum, runningSum - ceiling);}set.add(runningSum);}}}return maxSum;}public static void main(String[] args) {int[][] matrix = {{1, 0, 1}, {0, -2, 3}};int k = 2;MaxSumSubmatrix solution = new MaxSumSubmatrix();int maxSum = solution.maxSumSubmatrix(matrix, k);System.out.println("矩阵内部矩形区域的不超过 k 的最大数值和为：" + maxSum);}
}
上述代码中，使用了一个嵌套的循环来遍历矩阵的每一个可能的子矩阵。通过计算每一行的和，然后使用'TreeSet'来维护一个有序的前缀和集合。对于每个前缀和，在集合中查找不超过当前前缀和减去 k 的最大元素，更新最大数值和。最后返回最大数值和。在'main'方法中，构建了一个示例矩阵和 k 值，并调用'maxSumSubmatrix'方法计算并输出结果。
(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)