LC363. Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
Example:
Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2
这个题要找出所给矩阵的子矩阵，它包含的数字总和 <= k，求这样的子矩阵包含数字和最大是多少。感觉先找出子矩阵，然后求出最大的和，一想到求和又想用BIT，但是这个题求好多区间和，应该不是BIT。看到👇利用TreeSet的解法觉得很不错。
对于每一列利用TreeSet可以在subSum的子集里面找到最优解。
public class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
// using treeset which can search for boundaries
// for each rectangle, check the sum
if(matrix == null || matrix.length == 0) return 0;
int row = matrix.length, col = matrix[0].length;
int res = Integer.MIN_VALUE;
// rows >> cols so outer loop based on cols
for(int left = 0; left < col; left++){
// sum of each row from left to right, inclusive
int[] sums = new int[row];
for(int right = left; right < col; right++){
// each sub-retangle
for(int i = 0; i < row; i++) sums[i] += matrix[i][right];
// find curSum - sum <= k in O(lgn)
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(0);
int curSum = 0;
for(int sum: sums){
curSum += sum;
// ceiling return the lease item satisfy num > curSum - k
// the area of rectangle = curSum - sum, so smallest sum enables largest area
Integer num = set.ceiling(curSum - k);
if(num != null) res = Math.max(res, curSum - num);
set.add(curSum);
} // for sum
} // for right
} // for left
return res;
}
}
min(m,n)^2max(m,n)log(max(m,n))