Monotonic queue

A monotonic queue is a deque whose values always go down from front to back. It answers “what is the biggest value in this window?” as the window slides along a list, in O(1) per step on average.

The biggest value in a moving window

A window is a run of k values next to each other in a list (ARRS-3). Slide it one place at a time from the start to the end, and report the biggest value in each position. For [4, 2, 12, 3, 8, 5, 1, 7] and k = 3, the answers are [12, 12, 12, 8, 8, 7].

Calling max on each window costs k steps per window, so O(n × k) in total. A running sum can be updated when a value leaves the window, but a maximum cannot: when the biggest value leaves, you do not know the next biggest.

A deque kept in order

Keep a deque of places. A value is worth keeping only if it might still become the biggest in some later window. When a new value x arrives, every older value that is <= x can never be the biggest again: x is at least as big, and stays in the window longer. So remove them from the back.

Each step does three things:

• remove places from the back while their values are <= x, then add the new place at the back;
• remove the front place if it has slid out of the window;
• once the first window is complete, report the value at the front.

dq is a collections.deque of places. Here are the first two parts of the step, for place i with value x:

while dq and a[dq[-1]] <= x:
    dq.pop()              # can never be the biggest again
dq.append(i)
if dq[0] <= i - k:        # the front has left the window
    dq.popleft()

The third part, reporting a[dq[0]] once i reaches k - 1, is left to STAQ-P6.

Only one place can leave the front per step, because the window moves one place at a time. That is why a single if is enough there, while the back needs a while.

Why it is O(n)

The same counting as lesson 5: each place is added to the deque once and removed at most once, from one end or the other. So the whole run does n additions and at most n removals, at most 2n steps in all: O(n), whatever k is. After each step the deque holds at most k places.

Other ways, and their cost

The monotonic deque also speeds up some dynamic programming, where each answer is the best of the last k answers. You will meet that in DYNP.

Now try STAQ-P6, Biggest in each window.