239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:

You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow-Up:

Could you solve it in linear time?

Solution: Deque

import collections


class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        result = []
        q = collections.deque()

        for idx, num in enumerate(nums):
            if q and q[0] <= idx - k:
                q.popleft()
            while q and nums[q[-1]] <= num:
                q.pop()
            q.append(idx)
            if idx >= k - 1:
                result.append(nums[q[0]])

        return result

Lessons:

• Use deque to maintain a monotonic sequence.
• When push a new value, pop all smaller value before it.
• When the first (largest) value is out of window, popleft the first value.