239.Sliding Window Maximum

Tags: [queue], [deque], [window], [sliding_window], [sliding]

Com: {g}

Link: https://leetcode.com/problems/sliding-window-maximum/\#/description

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example,
Givennums=[1,3,-1,-3,5,3,6,7], andk= 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 assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Solution: Queue, Deque

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums or not k or k > len(nums):
            return []

        queue = collections.deque()
        size = len(nums)
        rest = []
        for w_end in xrange(size):
            w_start = w_end - k + 1
            while queue and queue[0] < w_start:
                queue.popleft()
            while queue and nums[queue[-1]] < nums[w_end]:
                queue.pop()

            queue.append(w_end)
            if w_end >= k - 1:
                rest.append(nums[queue[0]])

        return rest

Note:

• Time complexity = O(n), n is the number of elements in nums, because each elem only gets enqueue and dequeue once.