题目要求
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:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
and 2 is the max number no larger than k (k = 2).
Note:
1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过 k 的最大值，问子矩阵中元素的和为多少?
注：后面的文章中将使用 [左上角顶点坐标，右下角顶点坐标] 来表示一个矩阵，如 [(1,2),(3,4)] 表示左上角顶掉坐标为 (1,2)，右下角顶点坐标为(3,4) 的矩阵。用 S[(1,2),(3,4)] 表示该矩阵的面积。顶点的坐标系以数组的起始点作为起点，向下为 x 轴正方向，向右为 y 轴正方向。
思路一：暴力循环
如果我们将矩阵中的每个子矩阵都枚举出来，并计算其元素和，从而得出小于 K 的最大值即可。
这里通过一个额外的二维数组 S 缓存了 [(0,0), (i,j)] 的矩形的面积，可以通过 O(n^2)的时间复杂度完成计算，即 S[i][j] = matrix[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]，则矩形[(r1,c1),(r2,c2)] 的面积为S[r2][c2] -S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]。这种算法的时间复杂度为 O(N^4)，因为需要定位矩形的四个顶点，一共需要四圈循环，代码如下：
public int maxSumSubmatrix(int[][] matrix, int k) {
int row = matrix.length;
if(row == 0) return 0;
int col = matrix[0].length;
if(col == 0) return 0;
//rectangle[i][j]记录顶点为 [0,0],[i,j] 的矩形的面积
int[][] rectangle = new int[row][col];
for(int i = 0 ; i<row ; i++) {for(int j = 0 ; j<col ; j++) {int area = matrix[i][j];
if(i>0) {area += rectangle[i-1][j];
}
if(j>0) {area += rectangle[i][j-1];
}
// 减去重复计算的面积
if(i>0 && j>0) {area -= rectangle[i-1][j-1];
}
rectangle[i][j] = area;
}
}
int result = Integer.MIN_VALUE;
for(int startRow = 0 ; startRow<row; startRow++) {// 矩形的起点行
for(int endRow = startRow ; endRow<row ; endRow++) {// 矩形的结束行
for(int startCol = 0 ; startCol<col ; startCol++) {// 矩形的起始列
for(int endCol = startCol ; endCol<col ; endCol++) {// 矩形的结束列
int area = rectangle[endRow][endCol];
if(startRow > 0) {area -= rectangle[startRow-1][endCol];
}
if(startCol > 0) {area -= rectangle[endRow][startCol-1];
}
if(startRow > 0 && startCol > 0) {area += rectangle[startRow-1][startCol-1];
}
if (area <= k)
result = Math.max(result, area);
}
}
}
}
return result;
}思路二：利用二分法思路进行优化
对算法从时间上优化的核心思路就是尽可能的减少比较或是计算的次数。上面一个思路的我们可以理解为以 row1 和 row2 分别作为子矩阵的上边界和下边界，以 col2 作为右边界，要求找到一个左边界 col1，使得其划分出来的子矩阵中元素的和为小于等于 k 的最大值，即
max(S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)])
&& col1 < col2
&& S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)]<k`。换句话说，假如将 col2 左侧的所有以最左侧边为起点的子矩阵按照元素和从小到大排队，即将子矩阵 (row1, 0), (row2, colx) 其中 colx < col2 按照元素和从小到大排序，此时只需要在该结果中找到一个矩阵，其值为大于等于 S[(row1,0),(row2, col2)] - k 的最小值。此时得出的矩阵元素和差最大。这里采用 TreeSet 来实现 O(logN)的元素查找时间复杂度。
代码如下：
public int maxSumSubmatrix2(int[][] matrix, int k) {
int row = matrix.length;
if(row == 0) return 0;
int col = matrix[0].length;
if(col == 0) return 0;
//rectangle[i][j]记录顶点为 [0,0],[i,j] 的矩形的面积
int[][] rectangle = new int[row][col];
for(int i = 0 ; i<row ; i++) {for(int j = 0 ; j<col ; j++) {int area = matrix[i][j];
if(i>0) {area += rectangle[i-1][j];
}
if(j>0) {area += rectangle[i][j-1];
}
// 减去重复计算的面积
if(i>0 && j>0) {area -= rectangle[i-1][j-1];
}
rectangle[i][j] = area;
}
}
int result = Integer.MIN_VALUE;
for(int startRow = 0 ; startRow < row ; startRow++) {for(int endRow = startRow ; endRow < row ; endRow++) {
// 记录从 startRow 到 endRow 之间所有以最左侧边为起点的矩形的面积
TreeSet<Integer> treeSet = new TreeSet<Integer>();
treeSet.add(0);
for(int endCol = 0 ; endCol < col ; endCol++) {int area = rectangle[endRow][endCol];
if(startRow > 0) {area -= rectangle[startRow-1][endCol];
}
// 可以减去的左侧矩形的最小面积，即大于 S[(row1,0),(row2, col2)] - k 的最小值
Integer remain = treeSet.ceiling(area - k);
if(remain != null) {result = Math.max(result, area - remain);
}
treeSet.add(area);
}
}
}
return result;
}思路三：分治法
从上面两种思路，我们可以将题目演化成另一种思路，即对于任意以 row1 和 row2 作为上下边界的子矩阵，将其中每一列的元素的和记为sum[colx](0<=colx<col)，则生成一个长度为 col 的整数数组 sum。需要从该整数数组中找到一个连续的子数组，使得该子数组的和最大且不超过 k。
连续子数组的和是一道非常经典的动态规划的问题，它可以在 nlogn 的时间复杂度内解决。这里采用归并排序的思路来进行解决。本质上将数组以中间位置分割为左子数组和右子数组，分别求左子数组内和右子数组内最大的连续子数组和，并且在递归的过程中将左右子数组中的元素分别从小到大排序。接着判断是否有横跨中间节点的子数组满足题目要求，因为左右子数组分别有序，因此一旦遇到一个右边界，其和左边界构成的矩阵的元素的和超过 k，就可以停止右指针的移动。因此每次中间结果的遍历只需要 O(N)的时间复杂度。
代码如下：
public int maxSumSubmatrix3(int[][] matrix, int k) {
int row = matrix.length;
if(row == 0) return 0;
int col = matrix[0].length;
if(col == 0) return 0;
int result = Integer.MIN_VALUE;
int[] sums = new int[row+1];//sums[i]记录 startCol 到 endCol 列之间，0 行到 i 行构成的矩阵的面积
for(int startCol = 0 ; startCol<col ; startCol++) {int[] sumInRow = new int[row];//sumInRow[i]记录 startCol 到 endCol 列之间第 i 行所有元素的和
for(int endCol = startCol; endCol<col ; endCol++) {for(int endRow = 0 ; endRow<row ; endRow++) {sumInRow[endRow] += matrix[endRow][endCol];
sums[endRow+1] = sums[endRow] + sumInRow[endRow];
}
// 对 startCol 到 endCol 列之间所有的矩阵元素和构成的数组通过分治法找到最大的连续子数组
result = Math.max(result, mergeSort(sums, k, 0, sums.length));
if(result == k) return k;
}
}
return result;
}
public int mergeSort(int[] sums, int k, int start, int end) {
// 矩阵数组至少包含一个元素
if(end <= start + 1) return Integer.MIN_VALUE;
int mid = start + (end - start)/2, cacheIndex = 0;
// 对左侧递归计算，此时 sums 数组 [start,mid) 之间的元素已经有序
int ans = mergeSort(sums, k, start, mid);
if(ans == k) return k;
// 对右侧递归计算，此时 sums 数组 [mid,end) 之间的元素已经有序
ans = Math.max(ans, mergeSort(sums, k, mid, end));
// 缓存 sums 数组 [start,end) 之间排序的结果
int[] sortedSubSums = new int[end - start];
if(ans == k) return k;
for(int i = start, j = mid, m = mid ; i<mid ; i++) {while(j<end && sums[j] - sums[i] <= k) j++;// 找到第一个满足 [i,j) 之间的元素和大于 k，[i,j-1)之间的元素和小于等于 k 的连续子数组
if(j > mid) {ans = Math.max(sums[j-1] - sums[i], ans);
if (ans == k) return k;
}
while(m<end && sums[m] < sums[i]) sortedSubSums[cacheIndex++] = sums[m++];// 排序，通过每次将中间位置右侧比左侧当前位置小的元素全部复制有序数组缓存中
sortedSubSums[cacheIndex++] = sums[i];
}
System.arraycopy(sortedSubSums, 0, sums, start, cacheIndex);
return ans;
}