Monotonic queue — sliding max

Deque indices monotone decreasing — front max 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; முன் — window வெளியே evict.
• Min window — opposite monotone.