移动窗口的最小/最大值能否达到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[it]上的最大值，该算法产生O（N log（T））最坏情况。

我想知道有没有更好的算法？可能是O（N）算法

Answer 1

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

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

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

所谓的HGW算法需要两个与输入大小相同的中间缓冲区。对于大得离谱的输入（数十亿个样本），您可以将数据拆分为块并按块处理。

在html" target="_blank">排序中，您向前遍历数据，计算大小为T的块的累计最大值。你也一样向后走。每个样本都需要进行一次比较。最后，结果是这两个临时数组中的每一个都有一个以上的最大值。对于数据位置，可以同时对输入进行两次传递。

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

>

van Herk，“矩形和八角形核上局部最小和最大滤波器的快速算法”，模式识别字母13（7）：517-5211992（doi）

Gil，Werman，“计算二维最小、中值和最大滤波器”，IEEE模式分析和机器智能交易15（5）：504-5071993（doi）

Gil，Kimmel，“有效的扩张、侵蚀、打开和关闭算法”，IEEE Transaction on Pattern Analysis and Machine Intelligence24(12):1606-1617, 2002（doi）

（注：代码审查相关问题交叉发布。）

Answer 2

它被称为RMQ（范围最小查询）。实际上，我曾经写过一篇关于这一点的文章（使用c代码）。看见http://attiix.com/2011/08/22/4-ways-to-solve-±1-rmq/

或者您可能更喜欢wikipedia，范围最小查询

准备完成后，您可以在O（1）中获取任何给定范围的最大数量

Answer 3

O（N）可以使用Deque数据结构。它保存成对（值；索引）。

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