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:

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:

  1. The rectangle inside the matrix must have an area > 0.
  2. 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^2*n*log n)

详见代码

C++

 

 

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

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

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Max Sum of Rectangle No Larger Than K
本文地址:https://www.hrwhisper.me/leetcode-max-sum-rectangle-no-larger-k/

听说长得好看的已经打赏了

Leetcode , , . permalink.

4 thoughts on “leetcode Max Sum of Rectangle No Larger Than K

  1. 比如对于矩阵:

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

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

    应该是 [1,-2,4]吧

  2. 这道题有毛病:

    line 19: auto it = sums.lower_bound(sum – k);

    sums为什么是递增的呢? 如果有负数的话?

Leave a Reply

Your email address will not be published. Required fields are marked *