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

题目

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

示例:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

说明：

矩阵内的矩形区域面积必须大于 0。如果行数远大于列数，你将如何解答呢？

题解

获取每一行的一个前缀和，我们再根据列进行查找。 我们确定矩形的两列，然后从上往下一次遍历当前行的所属区域的和，也就是确定下边界，怎么确定上边界呢?我们用一个set集合存储遍历过的区域和，然后用lower_bound(pre_sum-k)二分查找大于等于pre_sum-k的第一个区域和，显然我们就能找到一个符合题意的上边界，且是不超过K的最大值。 详细过程见代码

代码

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { int m=matrix.size(),n=matrix[0].size(); vector<vector<int>> row_sum(m,vector<int>(n,0)); int ans=INT_MIN; row_sum[0][0] = matrix[0][0]; for(int i=0; i<m; i++) //获取每一行的前缀和 for(int j=1; j<n; j++) row_sum[i][j] = row_sum[i][j-1] + matrix[i][j]; for(int l=0; l<n; l++){ //确定左边界 for(int r=l; r<n; r++){ //确定右边界 set<int> list; list.insert(0); int pre_sum = 0; for(int i=0; i<m; i++){ //确定下边界 pre_sum += row_sum[i][r] - row_sum[i][l] + matrix[i][l]; set<int>::iterator target = list.lower_bound(pre_sum-k); //找到最能符合题意得上边界 if(target != list.end()){ ans = max(ans,pre_sum - *target); if(ans == k) return ans; //可以提前终止 } list.insert(pre_sum); } } } return ans; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。