【实战】ACM 选手图解 LeetCode 滑动窗口最大值

大家好呀，我是滑动窗口蛋。

今天解决滑动窗口最大值这道题，在 LeetCode 上有”滑动窗口“这四个字的基本上都是面试高频题。

学过计算机网络的小婊贝估计都知道个滑动窗口协议，别慌，这道题没辣么难顶。

滑动窗口呢，一般就用在数组或者字符串上，我们先从字面上来认识一下滑动窗口：

• 滑动：窗口可以按照一定的方向移动。
• 窗口：窗口大小可以固定，也可以不固定，此时可以向外或者向内，扩容或者缩小窗口直至满足条件。

了解了这些，下面开始直接肝题。

LeetCode 239：滑动窗口最大值

题意

大小为 k 的滑动窗口从整数数组 nums 的最左侧移到最右侧，只能看到滑动窗口中的 k 个数字，窗口每次向右移动一位。

返回滑动窗口的最大值。

示例

提示

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

• 1 <= k <= nums.length

题目解析

滑动窗口最大值，是用队列解决的经典问题，难度困难。

单调队列

在开始之前我先介绍一个之前没有讲过的队列，叫双端队列。

普通队列是限制仅在队尾进行插入，在队头进行删除操作的线性表，队列的插入叫做入队列，队列的删除叫做出队列。

而双端队列则是放开了这个限制，在队头和队尾两端都可以进行入队和出队操作的队列。

这么细看，其实对于队头或者队尾端，相当于是一个栈，后进的先出。

双端队列看上去这么的像栈和队列的结合体。

而有些时候，双端队列中还有受限的双端队列：一个是输出受限的双端队列，另一个是输入受限的双端队列。

输出受限的双端队列是：允许在一端进行入队和出队，但在另一端只允许入队的双端队列。

输入受限的双端队列是：允许在一段进行入队和出队，但在另一端只允许出队的双端队列。

输出受限的双端队列里，有一种情况，那就是队列里的各元素之间的关系具有单调性，这叫单调队列。

单调队列，顾名思义，所有队列里的元素都是按递增（递减）的顺序队列，这个队列的头是最小（最大）的元素。

哎呀妈呀，可算一步步的引出来了。