leetcode Max Sum of Rectangle No Larger Than K

leetcode Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:
1
2
3
4
5
Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2
The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

The rectangle inside the matrix must have an area > 0.

What if the number of rows is much larger than the number of columns?

题目地址：leetcode Max Sum of Rectangle No Larger Than K

题意：给定一个矩阵，求子矩阵中的和不超过K的最大值。

思路：

朴素的思想为，枚举起始行，枚举结束行，枚举起始列，枚举终止列。。。。。O(m^2 * n^2)

这里用到一个技巧就是，进行求和时，我们可以把二维的合并成一维，然后就变为求一维的解。

比如对于矩阵：

[1, 0, 1], [0, -2, 3]

进行起始行为0，终止行为1时，可以进行列的求和，即[1, -2, 4]中不超过k的最大值。

求和的问题解决完，还有一个是不超过k. 这里我参考了 https://leetcode.com/discuss/109705/java-binary-search-solution-time-complexity-min-max-log-max 的方法

使用了二分搜索。对于当前的和为sum，我们只需要找到一个最小的数x，使得 sum - k <=x，这样可以保证sum - x <=k。

这里需要注意，当行远大于列的时候怎么办呢？转换成列的枚举即可。

在代码实现上，我们只需要让 m 永远小于 n即可。这样复杂度总是为O(m^2nlog n)

详见代码

C++

class Solution {
public:
	int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
		if (matrix.empty()) return 0;
		int ans = INT_MIN,m = matrix.size(), n = matrix[0].size(),row_first=true;
		if (m > n) {
			swap(m, n);
			row_first = false;
		}
		for (int ri = 0; ri < m; ri++) {
			vector<int> temp(n, 0);
			for (int i = ri; i >= 0; i--) {
				set<int> sums;
				int sum = 0;
				sums.insert(sum);
				for (int j = 0; j < n; j++) {
					temp[j] += row_first ? matrix[i][j]: matrix[j][i];
					sum += temp[j];
					auto it = sums.lower_bound(sum - k);
					if (it != sums.end())
						ans = max(ans, sum - *it);					
					sums.insert(sum);
				}
			}
		}
		return ans;
	}
};

本题是leetcode 363 Max Sum of Rectangle No Larger Than K 题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/