Sliding Window Maximum

Question Description

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].

Solution

For this questions, it's very easy to come up with a solution of O(nlogn) using maximum heap. However, here we just illustrate a O(n) solution using deque.

Every time when we need to append an new element to the deque, if the last element of deque is smaller than the incoming element, we pop it out from right because it can never be considered in the loop. Then we push the new element in.

If the new element index is bigger than k, we can know that it is time to generate the maximum array appending the first element in the deque. If difference between the index of first element and index of the new one is k - 1, we know that it already have k elements in the deque, then we pop the first element from deque.

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