Monotonic Queue

A monotonic queue keeps candidates in useful value order while also respecting window order.

It is most commonly used for sliding window maximum or minimum.

Core Idea

The queue removes expired indexes from the front and removes weaker candidates from the back. The best candidate stays at the front.

Each index enters and leaves the queue at most once, so the algorithm can stay linear.

Python Example

from collections import deque
 
def sliding_window_max(values, k):
    queue = deque()
    result = []
 
    for i, value in enumerate(values):
        while queue and queue[0] <= i - k:
            queue.popleft()
 
        while queue and values[queue[-1]] <= value:
            queue.pop()
 
        queue.append(i)
 
        if i >= k - 1:
            result.append(values[queue[0]])
 
    return result

The front of the queue stores the index of the current window maximum.

Common Confusions

A monotonic queue is not sorted storage for all values. It only keeps candidates that can still become the answer.

It also differs from a heap because old indexes can expire by window position, not only by value.

When To Use It

Use a monotonic queue when a sliding window needs fast maximum or minimum queries while the window moves one step at a time.