To know when candidates expire. Candidates have both dominance order and expiry order, which a deque maintains at opposite ends.

The deque is a shortlist ordered twice: best value at the front, newest survival at the back. Remove candidates that are expired or permanently dominated.

What the function promises: Return window maxima for 1 <= width <= len(values). Invalid width raises ValueError.

from collections import deque

def sliding_maximum(values, width):
    if not 1 <= width <= len(values): raise ValueError("Invalid width")
    useful, answer = deque(), []
    for i, value in enumerate(values):
        while useful and useful[0] <= i-width: useful.popleft()
        while useful and values[useful[-1]] <= value: useful.pop()
        useful.append(i)
        if i+1 >= width: answer.append(values[useful[0]])
    return answer

assert sliding_maximum([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]
assert sliding_maximum([4], 1) == [4]

Work and storage: O(n) time because each index enters and leaves once; O(width) deque space.

When to recognize it: Candidates have both dominance order and expiry order, which a deque maintains at opposite ends.

Check before applying it: A multiset is needed when arbitrary deletions replace predictable left-to-right expiry.

Use two heaps with lazy deletion or an ordered multiset; one monotone deque preserves only extremes.