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

Question

我有输入数组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) 算法

Answer 1

O(N) 可以使用 Deque 数据结构。它包含对 (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