資訊專欄INFORMATION COLUMN
摘要：思路一暴力循環(huán)如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于的最大值即可。
題目要求
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?
現(xiàn)有一個由整數(shù)構(gòu)成的矩陣，問從中找到一個子矩陣，要求該子矩陣中各個元素的和為不超過k的最大值，問子矩陣中元素的和為多少?
注：后面的文章中將使用[左上角頂點(diǎn)坐標(biāo)，右下角頂點(diǎn)坐標(biāo)]來表示一個矩陣，如[(1,2),(3,4)]表示左上角頂?shù)糇鴺?biāo)為(1,2)，右下角頂點(diǎn)坐標(biāo)為(3,4)的矩陣。用S[(1,2),(3,4)]表示該矩陣的面積。頂點(diǎn)的坐標(biāo)系以數(shù)組的起始點(diǎn)作為起點(diǎn)，向下為x軸正方向，向右為y軸正方向。
如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于K的最大值即可。
這里通過一個額外的二維數(shù)組S緩存了[(0,0), (i,j)]的矩形的面積，可以通過O(n^2)的時間復(fù)雜度完成計算，即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]。這種算法的時間復(fù)雜度為O(N^4)，因?yàn)樾枰ㄎ痪匦蔚乃膫€頂點(diǎn)，一共需要四圈循環(huán)，代碼如下：
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]記錄頂點(diǎn)為[0,0],[i,j]的矩形的面積
int[][] rectangle = new int[row][col];
for(int i = 0 ; i0) {
area += rectangle[i-1][j];
}
if(j>0) {
area += rectangle[i][j-1];
}
//減去重復(fù)計算的面積
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 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;
}
思路二：利用二分法思路進(jìn)行優(yōu)化
對算法從時間上優(yōu)化的核心思路就是盡可能的減少比較或是計算的次數(shù)。上面一個思路的我們可以理解為以row1和row2分別作為子矩陣的上邊界和下邊界，以col2作為右邊界，要求找到一個左邊界col1，使得其劃分出來的子矩陣中元素的和為小于等于k的最大值，即
