Question same to problem 1499

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        #TC: O(len(nums))
        #SC: O(k)

        #keep a monontonely decreasing queue
        #The front(left) of the queue are the maximum value in the sliding window

        res = []
        Q = collections.deque([])
        #store element (value, idx)

        for idx, num in enumerate(nums):
            while len(Q) > 0 and idx - Q[0][1] >= k:
                Q.popleft()

            while len(Q) > 0 and num > Q[-1][0]:
                Q.pop()

            Q.append((num, idx))

            if idx >= k-1:
                res.append(Q[0][0])

        return res