LeetCode 239 - Sliding Window Maximum - 2022.12.31 solution

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """ How to solve it: From the way the window is sliding across the nums, you can imagine a deque
        where numbers are added to the right and popped off the left.  The tricky part is knowing exactly how
        to add to and pop from the deque.  If the deque contains every value, you'll need to look through it each
        time to find the max, which will make the solution O(n*k).
        We need some way to remove items from the deque when they're 'old'.
        I think one key observation you can make from looking at the first window in the first example ([1 3 -1])
        is that we don't need the deque to contain the '1', because the '3' will always be the max for that window
        and any future window (because the window will always move to the right).  So the starting data for the
        deque could be the 3 and the -1.  We'd want the -1 because it *could* conceivably be the max for the window
        as it moves to the right.  When the window moves to the right one spot, if the value was greater than 3
        (like, 4) we could discard the existing values in the deque (3 and -1) because they could never be the
        max anymore.  If the value was greater than -1 but less than 3, we could discard the -1 because it would
        never be the max anymore, but we'd need to keep the 3 for the current window.  And if the value was less
        than -1, we'd need to keep the 3, the -1, and the new value (in this case -3) because the 3 would be the
        max for the current window, the -1 could be the max when the 3 gets popped, and the -3 could end up being
        the max when both the 3 and -1 are no longer in the window.  All of this suggests maintaining the deque
        in decreasing order.
        """
        d = deque()
        res = []

        for i in range(len(nums) - k + 1):
            if not d:
                for j in range(k):
                    if not d:
                        d.append(i+j)
                    else:
                        while d and nums[i+j] > nums[d[-1]]:
                            d.pop()
                        d.append(i+j)
            elif i+k <= len(nums):
                while d and d[0] < i:
                    d.popleft()
                while d and nums[i+k-1] > nums[d[-1]]:
                    d.pop()
                d.append(i+k-1)
            res.append(nums[d[0]])
        return res