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

EN

使用Deque数据结构可以实现O(N)。它保存对(Value；Index)。

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

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

或者你可能更喜欢维基百科，Range Minimum Query

在准备之后，您可以获得O(1)中任意给定范围的最大值

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

这个问题的最有效算法是在1992和1993年提出的，分别由van Herk和Gil和Werman独立提出。该算法对每个样本恰好需要3次比较，与T的大小无关。

几年后，Gil和Kimmel进一步改进了算法，每个样本只需要2.5个比较。尽管方法的复杂性增加可能会抵消较少的比较(我发现越复杂的代码运行得越慢)。我从来没有实现过这个变体。

HGW算法需要两个大小与输入相同的中间缓冲区。对于大得离谱的输入(数十亿个样本)，您可以将数据分成块并按块进行处理。

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

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

(doi

• Gil，Werman，“计算2-D最小、中值和最大滤波器”，IEEE模式分析和机器智能学报15(5):504-507,1993年(doi)

• Gil，，“高效扩张、侵蚀、打开和关闭算法”，
• Transactions on Pattern Analysis and Machine Intelligence 24(12):1606-1617，2002年(doi)

(注:来自this related question on Code Review的交叉发布。)