本文主要是介绍力扣363.矩形区域不超过K的最大数值和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣363.矩形区域不超过K的最大数值和
-
前缀和
- 枚举上下边界,每次枚举将上下边界之间的同列元素加和
- 转化为一维前缀和问题,求Sr - Sl <= k的最大值,即Sl >= Sr - 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;}};
这篇关于力扣363.矩形区域不超过K的最大数值和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!