[Coderust] Find Maximum in Sliding Window

 

 

Problem

 

 

 

---

 

Solution

 

Use deque (double-ended queue) to store indices and a result array to keep track of the maximum integers for each window.

When pushing an index into the deque, pop every index that contains smaller integer than the current integer.

If current integer is less than the integer held by the index at the head, just append current index to the deque.

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import deque
        q = deque()
        result = []
        for i,curr in enumerate(nums):
            while q and nums[q[-1]] <= curr:
                q.pop()
            q.append(i)
            # remove the head index if it is not within the window (anymore)
            if q[0] == i - k:
                q.popleft()
            # start appending when the window is filled
            if i >= k-1:
                result.append(nums[q[0]])
        return result