假设我有一个大小为 N x M 的二维数组。我想打印出大小为 A x B 的每个子数组的最大值的总和。
例如，对于这个 3 x 3 数组，A = 2 和 B = 2。
Input:
1 2 3
4 5 6
7 8 9
输出应该是:
Output:
from (0, 0) to (1, 1): 5
from (0, 1) to (1, 2): 6
from (1, 0) to (2, 1): 8
from (1, 1) to (2, 2): 9
Answer: 5 + 6 + 8 + 9 = 28
我尝试过使用二维稀疏表，但它绝对不够快。如果可能的话，我正在尝试实现O(N * M)。
最佳答案
This answer描述了一种扩展一维(数组)算法以查找 maximum over a sliding window 的方法(请阅读方法 3，即使用双端队列的方法)。本质上:
- 找到 B 个元素的每个水平序列的最大值，从而有效地将矩阵减少到 N - B + 1 列。
- 找到 A 元素的每个垂直序列的最大值，从而有效地将矩阵缩减为 M - A + 1 行。
- 其余元素是您的窗口最大值，只需将它们相加即可。
关于algorithm - 所有大小为 A x B 的二维子数组的最大值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58948355/