Monotonic Queue — Sliding Window Max

Keep deque indices monotone decreasing so the front is always the current window maximum candidate.

Try this in Python

from collections import deque


def sliding_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

Key takeaways

• Pop smaller indices from the back—they can never be max again.
• Evict out-of-window indices from the front.
• Same pattern solves minimum window with the opposite monotonicity.