15

我有输入数组 A

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

我想要返回 B 的函数 Max(T,A) 表示 A 上的最大值超过上一个大小为 T 的移动窗口，其中

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

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

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

4

3 回答 3

32

使用 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
于 2012-08-30T10:44:28.327 回答
6

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

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

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

于 2012-08-30T09:51:40.833 回答
4

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

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

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

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

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

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

  • van Herk，“矩形和八边形内核上局部最小和最大滤波器的快速算法”，模式识别快报 13(7):517-521, 1992 ( doi )

  • Gil, Werman，“计算二维最小值、中值和最大值滤波器”，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 上的这个相关问题交叉发布。）

于 2018-04-01T17:29:19.903 回答