[leetcode 239] sliding window

Ideas ： A monotonous queue

• Maintain a two terminal queue , Store subscripts , The corresponding elements are in decreasing order .
• For each window , The maximum value is the first element of the monotone queue .

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = collections.deque()
        ans = list()

        for i, x in enumerate(nums):
            #  Pop up values not in the interval 
            if i >= k and window[0] <= i - k:
                window.popleft()
            
            #  Maintain monotonous queues 
            while window and nums[window[-1]] <= x:
                window.pop()
            window.append(i)
            
            #  Store results 
            if i >= k - 1:
                ans.append(nums[window[0]])
        
        return ans