Sliding Window Maximum

Question

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.

Tags

• dequeue
• Array

Thought

Reference: http://bookshadow.com/weblog/2015/07/18/leetcode-sliding-window-maximum/

Two solutions:

1. Naive solution: Generate the subsequence for the sliding window according to the index and obtain the maximum value.
2. Advanced solution: Use dequeue to store the index of the items in the array to represent the window in the order of the index. Append the new item at the end of the dequeue and remove all the numbers which are smaller than the new item in the former part of the dequeue such that the values of the elements in the dequeue are decreasing. Check the index of the first item in the dequeue, if it is out of the range for the current window, remove it.

Code

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dq = collections.deque()
        ans = []
        for i in range(len(nums)):
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()
            dq.append(i)
            if dq[0] == i - k:
                dq.popleft()
            if i >= k - 1:
                ans.append(nums[dq[0]])
        return ans