LC 0239 [H] Sliding Window Maximum - ALawliet/algorithms GitHub Wiki

keep the max at the front of the deque by popping the right (greedy)
we store the index instead of value in the deque so we can move the left of the window

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ideq = deque()
        res = []

        for r, x in enumerate(nums):
            # keep the index of the biggest number on the end of deq while moving r (greedy)
            while ideq and x > nums[ideq[-1]]:
                ideq.pop()
            ideq.append(r)

            # just make sure we move l
            l = r - k + 1
            if ideq[0] < l:
                ideq.popleft()

            # keep appending front of deq to build the answer
            if r >= k - 1:
                res.append(nums[ideq[0]])

        return res