• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

A window of width k slides across the array and at every stop we want its maximum. Recomputing that max by scanning all k elements each time is O(N·k), and it's wasteful because sliding by one position barely changes the window — one element leaves the left, one joins the right — yet we redo the whole scan from scratch.

# Brute Force (O(N * k) Time, O(1) Space)
res = []
for i in range(len(nums) - k + 1):
    window_max = float('-inf')
    for j in range(i, i + k):
        window_max = max(window_max, nums[j])
    res.append(window_max)
return res

A max-heap of the window's elements hands you the maximum instantly, but the element that slides out isn't at the top, so you can't cheaply delete it. The usual patch is lazy deletion: leave stale entries in the heap and only discard one when it surfaces at the top and turns out to be outside the window. That gets you to O(N log N).

# Max-Heap with Lazy Removal (O(N log N) Time, O(N) Space)
import heapq
heap = []  # stores (-val, index)
res = []
for i in range(len(nums)):
    heapq.heappush(heap, (-nums[i], i))
    if i >= k - 1:
        while heap[0][1] <= i - k:      # discard maxima that slid out of the window
            heapq.heappop(heap)
        res.append(-heap[0][0])
return res

True linear time comes from a monotonic deque. A deque (double-ended queue) lets you push and pop at both ends, and we need both ends here — which is exactly why a plain stack or queue won't do. We store the indices of elements that could still be the maximum of the current or some future window, and we keep their values decreasing from front to back, so the front index is always the current window's max.

Why are we allowed to throw indices away? An index becomes useless for two independent reasons. First, it slides off the left edge as the window advances — dead by position. Second, a newer element arrives that is greater than or equal to it: the newcomer is at least as large and will linger in the window longer, so the older one can never be the maximum again. That second rule is what keeps the deque decreasing. So at each step: pop from the back while the back's value is ≤ the new value, append the new index, drop the front if it has slid out of the window, and once the window is full read the front as the answer.

# Monotonic Deque (O(N) Time, O(k) Space)
from collections import deque
dq = deque()   # holds indices; their values stay decreasing front-to-back
res = []
for i in range(len(nums)):
    while dq and nums[i] >= nums[dq[-1]]:   # newcomer dominates the back
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:                      # front has slid out of the window
        dq.popleft()
    if i >= k - 1:
        res.append(nums[dq[0]])             # front is this window's maximum
return res

Every index is appended once and removed once, so the whole sweep is linear. The double-ended part earns its keep: stale maxima leave from the front, dominated newcomers-beaters leave from the back.