algorithm - 所有大小为 A x B 的二维子数组的最大值

Question

假设我有一个大小为 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)。

Answer 1

This answer描述了一种扩展一维(数组)算法以查找 maximum over a sliding window 的方法(请阅读方法 3，即使用双端队列的方法)。本质上:

1. 找到 B 个元素的每个水平序列的最大值，从而有效地将矩阵减少到 N - B + 1 列。
2. 找到 A 元素的每个垂直序列的最大值，从而有效地将矩阵缩减为 M - A + 1 行。
3. 其余元素是您的窗口最大值，只需将它们相加即可。