力扣363.矩形区域不超过K的最大数值和

力扣363.矩形区域不超过K的最大数值和

• 前缀和

  • 枚举上下边界，每次枚举将上下边界之间的同列元素加和
  • 转化为一维前缀和问题，求S_r - S_l <= k的最大值，即S_l >= S_r - k的最小值
  • 考虑用lowerbound，可以用一个有序集合存此前遍历过的前缀和

•   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++){//[i,j]的一维前缀和vector<int> s(n);//枚举下边界for(int j=i;j<m;j++){//随着j++,新增的一行和之前行对应元素合并for(int c=0;c<n;c++)s[c] += matrix[j][c];//存前缀和set<int> sumset{0};int cnt = 0;for(int v:s){   //当前前缀和cnt += v;auto lb = sumset.lower_bound(cnt-k);if(lb != sumset.end())ans = max(ans,cnt - *lb);sumset.insert(cnt);}}}return ans;}};