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.

Function Contract

sliding_window_max(values, k) expects a list of comparable values and a window size k with 1 <= k <= len(values).

It returns the maximum value for each contiguous window of length k, in left-to-right order.

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.

Step-by-Step Idea

For a sliding window maximum, an older smaller value can be removed when a newer larger value arrives. The newer value is at least as good for the current window and will remain available longer.

The front can also expire when it falls outside the current window.

Why It Works

The queue stores only candidates that could still become the maximum. Values smaller than a newer value are removed from the back because they cannot win in any future window that includes the newer value.

The queue also stores indexes, not just values, so the algorithm can remove candidates whose positions are outside the window.

Complexity

Each index is appended once, removed from the back at most once, and removed from the front at most once. The total time is O(n), and the queue uses O(k) space for window size k.

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.

Another common mistake is storing values only. Duplicate values make it hard to know which one expired, so indexes are safer.

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.

Do not use it for arbitrary range maximum queries where windows are not moving in a simple one-direction scan.

The Main Point

A monotonic queue combines window expiration with value dominance. It keeps only candidates that can still become the window answer.