计算移动最大值

Question

可能重复:
在大小为n的数组的大小为l的所有连续子数组中查找最小数

我有一个(大)数值数据(大小)数组,N并希望计算一个具有固定窗口大小的运行最大值的数组w.

更直接的是,我可以out[k-w+1] = max{data[k-w+1,...,k]}为k >= w-1(定义基于0的数组,如在C++中)定义一个新数组.

有没有更好的方法来做到这一点N log(w)？

[我希望在N没有依赖的情况下应该有一个线性的w,比如移动平均线,但找不到它.对于N log(w)我认为有一个排序的数据结构,它会做管理的方式insert(),delete()并extract_max()完全在log(w)以下大小的结构w-就像一个排序二叉树,例如.

非常感谢你.

Answer 1

确实有一种算法可以在O(N)时间内完成,而不依赖于窗口大小w.我们的想法是使用支持以下操作的聪明数据结构:

• 入队,为结构添加新元素,
• Dequeue,从结构中删除最旧的元素,和
• Find-max,返回(但不删除)结构中的最小元素.

这本质上是一个队列数据结构,支持访问(但不删除)最大元素.令人惊讶的是,正如之前的问题所示,可以实现这种数据结构,使得这些操作中的每一个都在分摊的O(1)时间内运行.因此,如果您使用此结构将w元素排入队列,那么在根据需要调用find-max时连续将其他元素出列并排入结构中,它将只需要O(n + Q)时间,其中Q是数字你提出的问题.如果您只关心每个窗口的最小值,则最终为O(n),而不依赖于窗口大小.

希望这可以帮助!