[LeetCode]Max Sum of Rectangle No Larger Than K

2D array的问题一般有几种解法，比较常见的有DP，或者转化成图用图的解法，比如BFS/DFS，Dijkstra等等。除此之外，我们有的时候还会转化成1D再用相应的解决1D问题的方法。这一题就是一个很好的例子，一开始可能我们没有很好的解决2D问题的思路，那么我们可以思考如果解决1D问题Max Sum Subarray No Larger Than K，其和Max Subarray的问题又是相关的。这里我们有一个限制是和不能超过k，我们只需要用BST存之前所有的presum，然后对于每个当前的数，找出BST中>=currPreSum - k的最小的数，假设1D array长度为n，时间复杂度O(n * log n)。那么我们可以将其扩展到2D，假设行的数目大于列，那么我们可以对列进行遍历，将不同的列的组合累加起来，然后用1D的方法来解。具体可以参考这个视频。如果列的数目大于行，我们只需要将矩阵转置然后求解即可。时间复杂度分析，我们要对列遍历时间min(m, n)^2，然后1D求解max(m, n) * log max(m, n)，时间复杂度min(m, n)^2 * max(m, n) * log max(m, n)，代码如下：

	class Solution {
	public:
	int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, res = INT_MIN;
	for(int l = 0; l < n; ++l)
	{
	vector<int> sum(m, 0);
	for(int r = l; r < n; ++r)
	{
	for(int i = 0; i < m; ++i)
	sum[i] += matrix[i][r];
	//1D max subarray no larger than k
	set<int> presum;
	presum.insert(0);
	int currSum = 0;
	for(int i = 0; i < m; ++i)
	{
	currSum += sum[i];
	auto it = presum.lower_bound(currSum - k);
	if(it != presum.end())res = max(res, currSum - *it);
	presum.insert(currSum);
	}
	}
	}
	return res;
	}
	};

view raw Max Sum of Rectangle No Larger Than K.cpp hosted with ❤ by GitHub