题目
给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
示例 1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2 输出：2 解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
示例 2：
输入：matrix = [[2,2,-1]], k = 3 输出：3
解题
方法一：前缀和+暴力枚举
首先记录前缀和
依次枚举左上角和右下角这两个点，
class Solution { public: int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { int m=matrix.size(),n=matrix[0].size(); int prefix[110][110]={0}; 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]+matrix[i-1][j-1]-prefix[i-1][j-1]; } } int res=INT_MIN; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ for(int p=i;p<=m;p++){ for(int q=j;q<=n;q++){ int cur=prefix[p][q]-prefix[i-1][q]-prefix[p][j-1]+prefix[i-1][j-1]; if(cur<=k){ res=max(res,cur); } } } } } return res; } };
方法二：前缀和+set+二分查找
矩形区域是由4条边来确定的，因此可以先固定上下两条边,和右边界
矩形的左边界，类似于两数之和的思路，可以采用二分查找的方式
存入set中，保证有序，可以采用二分查找的方式
为了满足right-left<=k,因此要保证左边界要大于等于 set.lower_bound(right-k)
class Solution { public: 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,0)); 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]+matrix[i-1][j-1]-prefix[i-1][j-1]; } } int res=INT_MIN; for(int top=1;top<=m;top++){ for(int bottom=top;bottom<=m;bottom++){ set<int> set; set.insert(0); for(int r=1;r<=n;r++){ int right=prefix[bottom][r]-prefix[top-1][r]; auto left=set.lower_bound(right-k); if(left!=set.end()){ int cur=right-*left; res=max(res,cur); } set.insert(right); } } } return res; } };
