Sliding Window Maximum

题目描述

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?

解题方法

方法1

最直观的方法是维护一个heap, sliding window用类似2 pointer的方法做， 然后heap可以每次快速找到max, 但是heap的插入删除操作都需要O(logn)

方法2

用一个head和tail都可以快速插入/删除的数据结构，我们可以想到deque. 而deque没有办法快速求max，那怎么办呢？我们想取得最大值的时间为 o(1), 并且可以快速delete,根据类似min stack的做法。我们在deque里只放 可以成为max的候选value,并且只在头部删去这个值的时候将它从deque中pop 出去。

那么在遇到比当前deque head大的value时，我们就应该head pop出去直到 head >= current value.

注意点

• 将新value加入deque的时候，是将tail部分比它小的值都pop出去
• 删除head的value时，是从popleft()

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

        length = len(nums)    
        result = []
        dq = deque()

        for i in range(length):
            # 将新的value加入到deque
            while dq and dq[-1] < nums[i]:
                dq.pop()
            dq.append(nums[i])
            # 如果多于k个element了，就要将头部的pop出去（如果nums[i-k]的value是头部的话）
            if i >= k and nums[i-k] == dq[0]:
                dq.popleft()
            # 将当前最大值加入结果
            if i >= k - 1:
                result.append(dq[0])


        return result

Reference