Monotonic Queue

A deque kept in decreasing order as values stream in — the front is always the current maximum. The same mechanism, restricted to a fixed window with eviction from the front, is exactly Sliding Window Maximum.

Category: Algorithmic Techniques
Time complexity: O(n)
Space complexity: O(n)

Pseudocode

for each incoming value:
  pop smaller values from the back
  push the new value
  front of deque = current max

Reference implementation

dq = deque()
for v in stream:
    while dq and dq[-1] &lt; v: dq.pop()
    dq.append(v)
    current_max = dq[0]

Open the interactive Monotonic Queue visualisation →