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

这里希望获得的是滑动窗口里的最大值。

可以看到，需要做的准备有下面这些：

队列空数组记录长度的整型

下面进行 for 循环，通过 left 和 right 分别表示滑窗窗口的两端，这里利用了 Python 语法上的一个技巧，将 left 和 right 可能出现的范围，映射在一起。

for left, right in zip(range(1-k, n+1-k), range(n)):

为了能让开始滑窗范围内的值有意义，需要将数组整体后移一个位置，即让 range(0, n) 变为 range(1, n+1), 再将窗口向前滑动 k 位，变为 range(1-k, n+1-k) 。这样就构成了 left 的范围，也就是下图中红线的区域。而 right 的范围则是蓝线的区域。

其中的队列作用是记录每个滑窗中的最大值。

在循环中，需要经过 4 个逻辑判断：

首先是，滑窗滑到右面新的位置的时候，需要判断弹出已无效的最大值

if left>0 and deque[0] == nums[left-1]: deque.popleft()

其次是，循环的检查队列中和滑窗右窗口的关系，如果队列尾部的值小于滑窗右窗口，则需要把队列中小的值弹出

while deque and deque[-1] < nums[right]: deque.pop()

之后是，将右窗口的值进行入队，这里需要注意的是滑窗移动的过程中，每一个右窗口的值都会入栈，如果它并不是最大值，则会在上面的判断中将它再弹出。

deque.append(nums[right])

最后是，在滑窗滑到有效范围内，将对应的结果记录到结果数组 res 中。

if left >= 0: res.append(deque[0])

答案

class Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        deque = collections.deque()        res, n = [], len(nums)        for i, j in zip(range(1-k, n+1-k), range(n)):            if i>0 and deque[0] == nums[i-1]: deque.popleft()            while deque and deque[-1] < nums[j]: deque.pop()            deque.append(nums[j])            if i >= 0: res.append(deque[0])        return res