移动窗口的最小/最大可以在O(N)中实现吗？

Question

我有输入数组A.

 A[0], A[1], ... , A[N-1]

我希望函数Max(T,A)返回B代表A在大小T所在的前一个移动窗口上的最大值

 B[i+T] = Max(A[i], A[i+T])

通过使用最大堆来跟踪当前移动窗口A [i]到A [i + T]的最大值,该算法产生O(N log(T))最坏情况.

我想知道有更好的算法吗？也许是O(N)算法

Answer 1

使用Deque数据结构可以实现O(N).它拥有对(价值;指数).

at every step:

  if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then 
     Deque.ExtractHead;
  //Head is too old, it is leaving the window

  while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do
     Deque.ExtractTail;
  //remove elements that have no chance to become minimum in the window

  Deque.AddTail(CurrentValue, CurrentIndex); 
  CurrentMin = Deque.Head.Value
  //Head value is minimum in the current window

Answer 2

它被称为RMQ(范围最小查询).实际上我曾经写过一篇关于它的文章(使用c ++代码).见http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/

或者您可能更喜欢维基百科,范围最小查询

准备之后,您可以获得任何给定范围的最大数量 O(1)

Answer 3

图像处理中有一个子领域，称为数学形态学。您正在实现的操作是该领域的核心概念，称为dilation。显然，这个操作已经被广泛研究，我们知道如何非常有效地实现它。

van Herk、Gil 和 Werman 于 1992 年和 1993 年独立提出了解决该问题的最有效算法。该算法需要对每个样本进行 3 次比较，与 的大小无关T。

几年后，Gil 和 Kimmel 进一步完善了算法，每个样本只需要 2.5 次比较。尽管方法复杂性的增加可能会抵消比较次数的减少（我发现更复杂的代码运行速度更慢）。我从未实现过这个变体。

HGW 算法，正如其名称，需要两个与输入大小相同的中间缓冲区。对于非常大的输入（数十亿个样本），您可以将数据分割成块并逐块处理。

按排序，您向前遍历数据，计算 size 块上的累积最大值T。你向后走也做同样的事情。其中每一项都需要对每个样本进行一次比较。最后，结果是这两个临时数组中每个值的最大值。对于数据局部性，您可以同时对输入进行两次传递。

我想你甚至可以做一个运行版本，其中临时数组的长度为 length 2*T，但这实现起来会更复杂。

• van Herk，“矩形和八角形内核上局部最小和最大滤波器的快速算法”，Pattern Recognition Letters 13(7):517-521, 1992 ( doi )

• Gil, Werman，“计算 2-D 最小值、中值和最大值滤波器”，IEEE Transactions on Pattern Analysis and Machine Intelligence 15(5):504-507，1993 ( doi )

• Gil, Kimmel，“高效的膨胀、腐蚀、开闭算法”，IEEE Transactions on Pattern Analysis and Machine Intelligence 24(12):1606-1617, 2002 ( doi )

（注意：从Code Review 上的相关问题交叉发布。）