LeetCode_MaxSlidingWindow.py

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        output = []
        
        if not nums or k <= 0:
            return output
        
        # The `Q` will store the indices of the largest element (so far) at the front of it.
        # i.e. Store indicies of elements in descending order (of the value of the element).
        from collections import deque
        Q = deque(maxlen=k)
        
        # The previous smaller elements are useless, so remove them (right-pop).
        for i in range(k):
            val = nums[i]
            while Q and val >= nums[Q[-1]]:
                Q.pop()
            Q.append(i)
        
        # Start from the `k-th` element and insert/append the index of the larger values into the `Q`.
        for i in range(k, len(nums)):
            val = nums[i]            
            output.append(nums[Q[0]])
            
            # If the Q[0] is obselete, left-pop them.
            while Q and Q[0] < (i-k+1):
                Q.popleft()
                
            while Q and val> nums[Q[-1]]:
                Q.pop()
            Q.append(i)
        if Q:
            output.append(nums[Q[0]])
        return output