参考文献
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
// 朴素做法是 O(n^2*m^2),可以优化到 O(n^2*mlgm),m=max(m,n)
// 固定两列,枚举i行,考虑 S(i)-S(j-1) <= k ==> S(j-1) >= S(i)-k,即找到大于等于S(i)-k的最小值
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> prefix(m+1, vector<int>(n+1));
for(int i=1; i<=m; ++i){
for(int j=1; j<=n; ++j){
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
}
}
// i,j,x,y 是前缀和下标
auto getPrefixSum = [&](int x1, int y1, int x2, int y2)->int {
// ++x1, ++y1, ++x2, ++y2;
return prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1];
};
int res = INT_MIN;
// i是左边列,j是右边列
for(int i=1; i<=n; ++i){
for(int j=i; j<=n; ++j){
set<int> pre_row_sum;
pre_row_sum.insert(0); //0 也是前缀和
// 枚举左右列边界,再枚举尾行
for(int x=1; x<=m; ++x) {
int sk = getPrefixSum(1, i, x, j);
// 通过二分查找哪一行最优化
auto iter = pre_row_sum.lower_bound(sk-k);
if(iter != pre_row_sum.end()){
res = max(res, sk - *iter);
}
pre_row_sum.insert(sk);
}
}
}
return res;
}
};