移动窗口的最小/最大值能在O(N)内实现吗？

Question

我有一个输入数组 A

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

我希望有一个名为Max(T,A)的函数，它返回变量A上移动窗口大小为T时的最大值B。

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

使用最大堆来跟踪当前移动窗口A [i]到A [i + T]上的最大值，该算法的最坏情况为O（N log（T））。我想知道是否有更好的算法？也许是O（N）算法。

- ipoppo

---

如果 A 是固定的而 T 可变，则可以进行 O（N * log（N）） 的准备工作，然后对于每个 T，您可以在 O(N) 时间内获得 B。 - iloahz

@Topro 听起来不错！你能在回答中加入准备步骤吗？谢谢！ - ipoppo

http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html - legends2k

Answer 1

使用双端队列数据结构可以实现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

- MBo

---

勇敢，适用于更一般的情况。 - iloahz

顶部的“if”应该改成“while”，以防我们能够从头部修剪多个值。例如，如果头部有两个具有相似索引值的元素，并且新的索引值足够前进，这意味着两个旧元素现在已过期。 - John Zwinck

@John Zwinck 不，索引是唯一的，它是元素的“年龄”。只需要检查“=”而不是第二个条件中的“<=”就足够了。 - MBo

使用易读的JavaScript实现：https://gist.github.com/shimondoodkin/f274d6e17c66a8b72779 - Shimon Doodkin

@Cris Luengo 不是的。每个项目都会被处理两次 - 推到尾部并从头或尾部提取，因此时间复杂度为O(N)。 - MBo

@Cris Luengo 不需要排序。最小的项目坐在队列头上，直到更好的项目取代它（删除所有项目（第二个运算符）或它变得太旧（第一个运算符））。 - MBo

Answer 2

它被称为RMQ(区间最小查询)。实际上，我曾经写过一篇关于此的文章（附带C++代码）。可以看看http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/，或者你可以选择维基百科Range Minimum Query。

准备工作完成后，你可以在O(1)的时间复杂度内得到任何给定范围内的最大数。

- iloahz

---

所以它需要额外的O(N log(N))空间吗？我花了很长时间才理解整个准备步骤，这本质上是动态规划构造 :) 但是，是的，我确实需要经常变化T。这种方法是否比其他方法更有优势？ - ipoppo

@dondonchi 为您返回任何查询(l, r)的最小值，无需修复T。 - iloahz

Answer 3

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

对于这个问题，最有效的算法是由Van Herk和Gil以及Werman在1992年和1993年分别提出的。这个算法每个样本只需要3次比较，与T的大小无关。

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

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

简而言之，您向前遍历数据，计算大小为T的块的累积最大值。您向后执行相同的操作。每个操作每个样本只需要一次比较。最后，结果是这两个临时数组中每个值的最大值。为了数据局部性，您可以同时对输入进行两次通行证。

我猜你甚至可以做一个运行版本，其中临时数组的长度为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相关问题上。）

- Cris Luengo