solved 'Sliding Window Maximum' on LeetCode https://leetcode.com/problems/sliding-window-maximum/

slide_window_max.py

# Maintain a deque where the first element is the max
# of the window. 
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer[]}
    def maxSlidingWindow(self, nums, k):
        results = []
        # Element in the window should be (index, val).
        window = collections.deque()
        for i, ele in enumerate(nums):
            # Remove out-of-bound element.
            if window and i - window[0][0] >= k:
                window.popleft()
            # Squeeze the window.
            while window and window[-1][1] <= ele:
                window.pop()
            window.append((i, ele))
        
            # Record the max in the window.
            if i >= k - 1:
                results.append(window[0][1])
        
        return results