Class Solution

239-Sliding-Window-Maximum/Sliding_window_maximum.py:3–40

import collections

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        # Result list to store the maximum of each sliding window
        output = []
        
        # Deque to store indices of useful elements in the current window
        # The deque will always be in decreasing order of their values in nums
        q = collections.deque()
        
        # Left (l) and right (r) pointers for the sliding window
        l = r = 0

        # Iterate until the right pointer reaches the end of the array
        while r < len(nums):
            # Remove elements smaller than the current element nums[r]
            # from the back of the deque, since they can’t be maximum anymore
            while q and nums[q[-1]] < nums[r]:
                q.pop()

            # Add the current index to the deque
            q.append(r)

            # Remove indices from the front of the deque that are out of the current window
            if l > q[0]:
                q.popleft()

            # If the window has reached size k, start adding maximums to output
            if (r + 1) >= k:
                # The element at the front of the deque is the maximum for this window
                output.append(nums[q[0]])
                # Move the left boundary to slide the window forward
                l += 1

            # Move the right boundary to expand the window
            r += 1

        # Return the list of maximums for each window
        return output


# Test the solution