剑指 Offer-59I-滑动窗口的最大值

原题链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

image.png

解题思路：

1. 维护一个双向队列；
2. 当新加入的元素与队列首元素deque[0]相等时，则首元素出列；
3. 当新加入元素大于队列内元素时，将队列内元素出列，保证队列是单调递减的；
4. 每轮加入新元素，取队列的首元素deque[0]即该滑动窗口内的最大值。

Python3代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 最小队列
        if not nums: return []
        deque = collections.deque()
        res = []
        for i in range(k):  # 前k个值
            while deque and deque[-1] < nums[i]:
                deque.pop()
            deque.append(nums[i])
        res.append(deque[0])
        for i in range(k, len(nums)): # 后面的元素
            if deque[0] == nums[i-k]: # 滑动窗口的头元素
                deque.popleft()
            while deque and deque[-1] < nums[i]:
                deque.pop()
            deque.append(nums[i])
            res.append(deque[0])
        return res

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 暴力解法
        if not nums: return []
        ans = []
        for i in range(k, len(nums)+1):
            idx = max(0, i-k)
            ans.append(max(nums[idx:idx+k]))
        return ans