如何在给定数组中找到某个固定给定长度的每个子数组的最大值

Question

我们给出了一个由n个元素和一个整数k组成的数组.假设我们想在数组中滑动长度为k的窗口,报告每个窗口中包含的最大值.例如,给定数组

15  10   9  16  20  14  13

给定长度为4的窗口,我们将输出

[15  10   9  16] 20  14  13   ---> Output 16
 15 [10   9  16  20] 14  13   ---> Output 20
 15  10 [ 9  16  20  14]  13  ---> Output 20
 15  10   9 [16  20  14  13]  ---> Output 20

结果就是这样

16  20  20  20

我通过跟踪每个点上窗口的最大元素来解决问题,但是当最大元素滑出窗口时遇到了问题.那时,我想不出一个快速的方法来弄清楚剩下的最大元素是什么.

有谁知道解决这个问题的有效算法？

Answer 1

这个较早的问题讨论了如何在O(1)时间内构建支持insert,dequeue和find-min的队列数据结构.请注意,这不是标准优先级队列,而是一个队列,在任何时候您都可以在O(1)时间内找到它包含的最小元素的值.您可以轻松修改此结构以支持O(1)中的find-max而不是find-min,因为这与此特定问题更相关.

使用此结构,您可以在O(n)时间内解决此问题,如下所示:

1. 将数组的前k个元素排入特殊队列.
2. 对于数组其余部分中的每个元素:
   1. 使用队列的find-max操作报告当前子范围的最大元素.
   2. 从队列中取出一个元素,留下旧范围的最后一个k-1元素.
   3. 将序列中的下一个元素排入队列,使队列现在保持序列的下一个k元素子范围.

这需要总共O(n)时间,因为您访问每个数组元素一次,每次最多一次入队和出列一次,并且将find-max调用恰好nk次.我认为这很酷,因为复杂性与k无关,最初看起来并不一定是可能的.

希望这可以帮助!谢谢你提出一个很酷的问题!