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过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)