滑动窗口的最大值

题目

解题思路

直接遍历，是O(n×k)的时间复杂度。数组长度为n，窗口大小为k。

能够实现O(N)的时间复杂度？

思考：如何在每次窗口滑动后，将“获取窗口内最大值”的时间复杂度从O(k)降低至O(1)。
参考题目：包含min函数的栈。

维护一个单调递减的队列，因为需要左边弹出（不在窗口范围），右边压入，使用双端队列来实现这个数据结构。
因为需要判断元素是否在窗口内，因此队列存储索引。

保证：deque中只要的第一个元素永远是当前窗口的最大值。

代码

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque = collections.deque()
        res = []
        for i, num in enumerate(nums):
            while deque and deque[0] <= i - k: deque.popleft() # outdate indices
            while deque and num > nums[deque[-1]]: deque.pop()
            deque.append(i)
            if i >= k - 1:
                res.append(nums[deque[0]])
        return res