我们给出一个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
我正在通过跟踪每个窗口的最大元素来处理这个问题,但是当最大的元素从窗口中滑出时遇到问题.在那一点上,我想不出一个快速的方法来找出最大的剩余元素.
有没有人知道一个有效的算法来解决这个问题？
解决方法
This older question讨论如何在O(1)时间内构建支持insert,dequeue和find-min的队列数据结构.请注意,这不是一个标准的优先级队列,而是一个队列,您可以随时在O(1)时间内找到它包含的最小元素的值.您可以轻松地修改此结构,以支持O(1)中的find-max,而不是find-min,因为这与此特定问题更相关.
使用这种结构,可以在O(n)时间内解决这个问题,如下所示：
将阵列的前k个元素排队到特殊队列中.
>对于数组的其余部分的每个元素：
>使用队列的find-max操作来报告当前子范围的最大元素.
>从队列中取出一个元素,将旧范围的最后一个k-1元素保留在适当位置.
>从序列中排队下一个元素,导致队列现在保存序列的下一个k元素子范围.
这总共需要O(n)个时间,因为您访问每个数组元素一次,最多一次排队和排队,最后调用find-max n-k次.我认为这是非常酷的,因为复杂性独立于k,最初似乎并不一定是可能的.
希望这可以帮助！谢谢你提出一个很酷的问题！