Geek Answers Handbook

Can the min / max of a moving window reach in O (N)?

I have an input array A

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

I need the Max (T, A) function, which returns B, represents the maximum value on A compared to the previous moved window of size T, where

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

Using the maximum heap to track the maximum value for the current moving windows A [i] to A [i + T], this algorithm gives the worst case O (N log (T)).

I would like to know if there is a better algorithm? Perhaps the O (N) algorithm

+8
heap arrays algorithm max min
source share
2 answers

O (N) is possible using the Deque data structure. It contains 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
+19
source share

it is called RMQ (minimum range query). In fact, I once wrote an article about this (with C ++ code). See http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/

or you may prefer wikipedia, Minimum range request by range

after preparation, you can get the maximum amount of any given range in O(1)

+6
source share

More articles:


All Articles