A NEWER, BIGGER VALUE MAKES EVERY SMALLER VALUE TO ITS LEFT USELESS. THEY CAN NEVER BE THE MAX WHILE IT STANDS. SO KEEP ONLY A DECREASING RUN OF CANDIDATES BY INDEX, THE BIGGEST AT THE FRONT. DROP THE FRONT WHEN IT SLIDES OUT OF THE WINDOW, AND DROP THE BACK WHILE A NEW VALUE OUTGROWS IT. THE FRONT IS ALWAYS THIS WINDOW MAX.

GOLD IS THE DEQUE FRONT, THIS WINDOW MAX. TAN TILES ARE THE REST OF THE DEQUE, A DECREASING RUN OF CANDIDATES. BLUE TILES SIT INSIDE THE WINDOW BUT WERE OUTGROWN AND DROPPED. R RIDES THE NEW INDEX. THE DEQUE SHELF LISTS EACH STORED INDEX AND THE NUM IT POINTS TO, A DECREASING RUN, WHILE RES COLLECTS EACH WINDOW MAX.

1def max_sliding_window(nums, k):2    dq = deque()  # from collections3    res = []4    for r in range(len(nums)):5        if dq and dq[0] <= r - k:6            dq.popleft()7        while dq and nums[dq[-1]] < nums[r]:8            dq.pop()9        dq.append(r)10        if r >= k - 1:11            res.append(nums[dq[0]])12    return res