> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/hua-dong-chuang-kou/239-hua-dong-chuang-kou-zui-da-zhi.md).

# \[239]\[困难]\[队列] 滑动窗口最大值

## 题目描述

[239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/) [剑指 Offer 59 - I. 滑动窗口的最大值](https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

```
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[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
```

提示：

* 1 <= nums.length <= 10^5
* -10^4 <= nums\[i] <= 10^4
* 1 <= k <= nums.length

## 解题思路

与[\[155\]\[简单\]\[栈\] 最小栈](https://github.com/garnetow/garnetbook/tree/127b922b35ee9796c56f1edfb2117d4992fa9191/Algorithm/栈/155-最小栈.md)中的解题思路类似, 本题也需要构造一个**辅助数据结构**, 用来存储一些中间值, 辅助求解每个窗口对应的最大值. 题目中, 滑动窗口的移动形式, 其实就是**队列**这种数据接口元素入队和出队的方式, 那么在选取辅助结构时, 首先考虑的就是使用辅助队列.

与最小栈的辅助栈直白的作用不同, 本题中辅助队列的使用方式不是很直观. 我们要利用对接的特殊性质, 观察原始列表中前后两个元素`a`和`b`, `a`在`b`之前, 如果`a`小于`b`, 那么在`b`出现之后, `a`就绝不可能在任何一个窗口中是最大值, 换句话说, 如果遇到了这种关系的`a`和`b`, 在`b`出现的时候, **`a`就没有记录的必要了**, 就可以被抛弃掉了.

秉承这种思路, 我们设计辅助队列的存储内容和更新方式. 与辅助栈元素与主栈一一对应的关系不同, 辅助队列的更新逻辑程是这样的:

* 对于新来的数字, 我们从队列的尾部开始, 依次判断尾部的元素是否小于这个新的数字`num`, 如果小于, 则就遇到了上面所述的场景, 因此将队尾元素弹出抛弃, 继续检查新的队尾元素是否符合条件, 直到队列中没有任何元素, 或队尾的元素不小于`num`
  * 这样得到的队列是一个**递减序列**, 而队列的首个元素, 就代表了在当前窗口下的最大值
* 然后考虑被移出窗口的数字`last`
  * 如果`last`在被移出之前, 不是窗口中的最大值, 那么它肯定不在队列中, 因为在窗口最大值入栈的过程中(或者更早), `last`就已经被移出队列了
  * 如果是最大值, 那么它肯定是在队列的首位. 我们可以通过比较移出窗口的数字和队列首位的元素值是否相等, 来判断当前队列的最大值是否应该被移出, 如果满足, 则将队列的首位(最左端)的元素移出

可以看到我们使用的辅助队列是一个双向队列. 元素从右端添加, 从左右两端都可能弹出. 那么会不会出现辅助队列超长(超过窗口长度`k`)的现象呢, 因为这意味着还有窗口之外的元素被考虑, 从而得到的结果可能错误.

如果队列的长度等于窗口的大小, 说明当前窗口的每一个值都在队列中, 而按照添加的逻辑, 说明当前窗口的元素肯定是满足**递减**规律的, 否则就会有元素被踢出队列. 而这又说明窗口中的第一个元素就是窗口的最大值. 那么在新的元素进入时, 原窗口中第一个元素被移出窗口, 而它也是对应的最大值, 根据规则也会被移出队列, 新的元素被添加到队列中.

因此按照先判断剔除最大元素, 然后调整队列内容, 添加新元素的顺序操作, 就不可能出现辅助队列超长现象. 从而保证了结果的正确性.

```python
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k == 1:
            return nums

        n = len(nums)
        deq = deque()

        def adjust(num, last):
            if last is not None and last == deq[0]:
                deq.popleft()
            while deq and deq[-1] < num:
                deq.pop()
            deq.append(num)

        res = []
        for i, num in enumerate(nums):
            if i < k - 1:
                adjust(num, None)
            else:
                adjust(num, nums[i - k])
                res.append(deq[0])
        return res
```