Surprisingly, the easily accessible descriptions of this algorithm are not that easy to understand, so the trick is this:
As you slide a window of length m over your list of length n, you maintain a deque of all the elements in the current window that might, at some point, become the maximum in any window.
An element in the current window might become the maximum if it is greater than all the elements that occur after it in the window. Note that this always includes the last element in the current window.
Since every element in the deque is > all the elements after it, elements in the deque are monotonically decreasing, and the first one is therefore the maximum element in the current window.
As the window slides one position to the right, you can maintain this deque as follows: remove all the elements from the end that are <= the new element. Then, add the new element to the end of the deque. If the element that drops off the front of the window is the first element in the deque, then remove it. Since each element is added and removed at most one time, the total time required to maintain this deque is in O(n).
To make it easy to tell when an element at the front of the deque is falls out of the window, store the elements’ indexes in the deque instead of their values.
Here’s a reasonably efficient python implementation:
def windowMax(listi, m):
# the part of this list at positions >= qs is a deque
# with elements monotonically decreasing. Each one
# may be the max in a window at some point
q = []
qs = 0
listo=[]
for i in range(len(listi)):
# remove items from the end of the q that are <= the new one
while len(q) > qs and listi[q[-1]] <= listi[i]:
del q[-1]
# add new item
q.append(i)
if i >= m-1:
listo.append(listi[q[qs]])
# element falls off start of window
if i-q[qs] >= m-1:
qs+=1
# don't waste storage in q. This doesn't change the deque
if qs > m:
del q[0:m]
qs -= m
return listo