Queue (Java) - ShuweiLeung/Thinking GitHub Wiki

该页笔记始于"2018.6.10"，结于“2018.6.10”，使用Java语言

Queue类题目只有5道，其中2道为免费，3道为收费题

1.（363:Hard）（非常经典题）Max Sum of Rectangle No Larger Than K

  • 这道题给了我们一个二维数组，让我们求和不超过的K的最大子矩形，那么我们首先可以考虑使用brute force来解，就是遍历所有的子矩形，然后计算其和跟K比较，找出不超过K的最大值即可。就算是暴力搜索，我们也可以使用优化的算法，比如建立累加和，个人感觉和DP动态规划相似。
  • 当遍历到(i, j)时，我们计算sum(i, j)，表示矩形(0, 0)到(i, j)的和，然后我们遍历这个矩形中所有的子矩形，利用之前的sum矩阵信息，计算其每个矩形的和并与K比较，这样就可以遍历到原矩形的所有子矩形。具体实现思路参看代码及注释。（beat 26%）
  • 参考链接：博客中文讲解

上面的思路是最直接的解法，该题还有其他更高效的方法如二分查找、动态规划DP、队列等，下次复习时参看discuss仔细研究