239.md

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. Return the max sliding window.

example
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

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

Note: You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

思路

使用一个deque d存储窗口中的第一大，第二大，第三大....数据的索引,维持着d=[i1,i2,i3...in] nums[i1]>nums[i2]>nums[i3]....nums[in]。
遍历数据时将新的数n和最后一个值比较，如果n>nums[in]则将nums[in] 删除，继续往后比较in-1直到nums[ix]>n,然后将n的索引j放到deque的后面。
如果i1在当前窗口范围内，那么nums[d[0]]就是max当前窗口max值，判断i1是否在窗口内 d[0]>j-k(j为遍历nums的下标，也就是新数的下标，也就是窗口
的最右边的数的下标)，如果不在就将popleft

代码

解法1

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        output = []
        d = collections.deque()
        for i, n in enumerate(nums):
            #将比当前n元素小的pop掉
            while d and nums[d[-1]] < n:
                d.pop()
            d.append(i)
            #i-k就是窗口左边外的第一个元素的索引
            if d[0]<=i-k:
                d.popleft()
            #如果k=3,则i为 0,1的时候就不需要append
            if i>=k-1:
                output.append(nums[d[0]])
        return output