[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)，代码如下：