Can min/max of moving window achieve in O(N)?

Question

I have input array A

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

I want function Max(T,A) which return B represent max value on A over previous moving window of size T where

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

By using max heap to keep track of max value on current moving windows A[i] to A[i+T], this algorithm yields O(N log(T)) worst case.

I would like to know is there any better algorithm? Maybe an O(N) algorithm

Answer 1

O(N) is possible using Deque data structure. It holds pairs (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