Sliding Window Maximum

239. Sliding Window Maximum

Solution

1. Use a queue to maintain the maximum at each position.

2. If a leftmost index in the queue is outside current window, pop it out.

3. If the end of the queue is smaller than curr, it will no longer be the maximum in the following sliding window, pop it out.

4. Push curr in.

5. The leftmost of the queue is the maximum for curr window.

   def maxSlidingWindow(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    queue = collections.deque()
    res = []
    for i in range(len(nums)):
        while len(queue) != 0 and queue[0] < i - k + 1:
            queue.popleft()
           
        while len(queue) != 0 and nums[queue[-1]] < nums[i]:
            queue.pop()
        queue.append(i)
           
        if i >= k - 1:
            res.append(nums[queue[0]])
           
    return res