可分钟速度移动在O（N）窗口实现的/最大值？(Can min/max of moving windo

我有输入数组A

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

我想函数max（T，A），其在尺寸T，其中的以前移动窗口返回B表示最大值上甲

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

通过使用最大的堆跟踪最大值的当前移动窗口A [1]到A [1 + T]，该算法产量O（N日志（T））最坏情况。

我想知道有没有更好的算法？ 也许一个O（N）的算法

Answer 1:

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

Answer 2:

这就是所谓的RMQ（范围最小查询）。 其实我曾经写过有关的文章（用C ++代码）。 见http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/

或者你可能更喜欢在维基百科， 范围最值查询

配制后，你可以在任何给定的范围内的最大数量O(1)

Answer 3:

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

此问题的最有效的算法提出了在1992年和1993年，自主面包车海尔克，以及吉尔和Werman。 该算法需要独立的大小的每个样品恰好3个比较， T 。

几年后，吉尔和Kimmel进一步完善了算法需要每个样品只有2.5比较。 虽然该方法的复杂性增加可能会抵消较少的比较（我发现更复杂的代码运行更慢）。 我从来没有实现这个变体。

该HGW算法，因为它是所谓的，需要同样大小的输入的两个中间缓冲器。 对于大的离谱的投入（10亿样本的），你可以将数据分割成块，并对其进行处理块明智。

在排序，您可以通过数据向前走，计算过大小的块，累计最大T 。 你做同样的行走落后。 每个这些需要每采样1个比较。 最后，结果是最大超过在每个这两个临时阵列中的一个值。 对于数据位置，你可以在同一时间做在输入两遍。

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

• 面包车海尔克，“A快速算法局部最小值和上矩形和八边形的内核最大值过滤器”，模式识别快报13（7）：517-521，1992（ DOI ）

• 吉尔，Werman， “计算2-d分钟，中值和最大滤波器”，模式分析与机器智能的IEEE交易15（5）：504-507，1993（ DOI ）

• 吉尔，金梅尔，“高效膨胀，腐蚀，开，闭算法”，模式分析与机器智能24（12）IEEE交易：1606年至1617年，2002年（ DOI ）

（注：从横贴在代码审查此相关的问题 。）

文章来源: Can min/max of moving window achieve in O(N)?