239. Sliding Window Maximum

利用deque，在deque里維護(hù)一個不遞增序列就可以了

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