遍历矩形的上边界和下边界,将二维问题降为一维问题。
在遍历一维的时候,使用前缀和记录,选择符合条件的Sr 和 Sl
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int ans = INT_MIN;
int M = matrix.size(), N = matrix[0].size();
for (int i = 0; i < M; i++) {
vector<int> colume(N, 0); //一列的和
for (int j = i; j < M; j++) {
for (int c = 0; c < N; c++) {
colume[c] += matrix[j][c];
}
int num = 0;
set<int> sumSet{
0}; //目前出现了的前缀和
for (int c = 0; c < N; c++) {
num += colume[c];
auto Sl = sumSet.lower_bound(num - k);
if (Sl != sumSet.end()) {
ans = max(ans, num - *Sl);
}
sumSet.insert(num);
}
}
}
return ans;
}
};