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

Follow up:

Could you solve it in linear time?

解题方法

brute force

维护window,每次遍历找最大值，O(nk)

max heap

维护max heap, O(nlogk)

deque

我们可以从这个window移动的过程找出规律，因为window移动时总是去掉开头 的数字，有点像queue,而我们每次又要在末尾加上新的数字，所以这种首尾都要 操作的数据结构应该用deque.

那么如何找最大值呢？通过观察可以发现，如果后面出现了一个大的数，那么它 前面比它小的数其实我们就不用再记录了，因为不会用它们作为最大值，将它们 pop出去的时候也不影响当前的最大值。

所以每次遇到新的值时，我们就将deque后面比它小的数都pop出去。这样deque[0] 永远保持的是当前window里的最大值。

Solution

from collections import deque

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []
        result = []
        dq = deque()
        for idx, num in enumerate(nums):
            while dq and nums[dq[-1]] < num: # pop smaller elements
                dq.pop()
            dq.append(idx) # save index in the deque
            if idx - k == dq[0]: # if idx-k is the first element's index, should remove
                dq.popleft()
            if idx >= k - 1: # add each window's max
                result.append(nums[dq[0]])
        return result

Reference