力扣题目链接
此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
第一层：暴力法为什么不行？（你的想法）
你说的“直接比较每k个数字里最大的”叫暴力滑动。
假设数组长度n=100000，窗口大小k=50000。
每滑动一次，你就要比较 50000 次，一共要滑动 50001 次。总计算量是 25亿次，绝对超时。
第二层：单调队列到底在干嘛？（核心思想）
单调队列不是在“找最大值”，而是在维护一个“最大值候选人”的名单，并且按出场顺序排好队。
关键洞察：当窗口滑动时，一个新元素进来了。如果这个新元素比队列里末尾的某些旧元素还大，那么那些旧元素就永远不可能成为最大值了（因为它们比新元素小，而且还比新元素先过期）。所以，直接把那些没用的旧元素从队尾踢出去。
这就是“单调递减队列”名字的由来——队列里从头到尾，数值越来越小。
第三层：为什么不需要精确弹出“被移除的那个元素”？（解决你的最大疑问）
你问：“已经排序之后的队列，怎么能把窗口要移除的元素弹出呢？”
答案是：我们根本不关心它是不是在队列里，我们只在它“恰好是队首”时才弹出它。
请看下面这个活生生的例子，你就全明白了：
数组[5, 3, 4, 1]，窗口k=3。
窗口 [5, 3, 4]：
5 进队：
[5]3 进队：
[5, 3]（比5小，留着备用）4 进队：发现队尾的
3比4小，把3踢掉（因为3没4大，还比4先过期，永无出头之日）。队里变成[5, 4]。最大值= 队首
5。
窗口滑动，移除 5，加入 1：
关键操作：要移除的正是
5。此时一看，队首正好是
5，把它弹出！队列变成[4]。加入 1，比4小，留在队尾：
[4, 1]。最大值= 队首
4。完美！
如果移除的元素不在队首呢？比如窗口里是[4, 1, 2]，队里是[4, 2]（1早就被2踢掉了）。当窗口移除4时，队首弹出4，剩下[2]。当窗口要移除1时，因为 1 早就不在队列里了，所以队列什么都不用做。因为 1 根本不可能是最大值，我们根本不需要关心它何时被移除。
这个操作让每个元素最多进出队列一次，总时间直接从O(n*k)降为O(n)。
例如 数组：[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小k = 3。
队列里存的是下标（方便判断过期），为了你看得懂，我写成值(下标)。
| 步骤 | 当前元素 (i) | 1. 清理过期（队首下标 < i-2 就弹出） | 2. 清理弱者（队尾值 < 新值就弹出） | 3. 入队后队列状态 | 4. 当前窗口最大值（队首值） |
|---|---|---|---|---|---|
| 1 | 1 (i=0) | 窗口未满，无需过期 | 队空，无人可弹 | [ 1(0) ] | 窗口未满，不输出 |
| 2 | 3 (i=1) | 窗口未满，无需过期 | 队尾 1 < 3，弹出1 | [ 3(1) ] | 窗口未满，不输出 |
| 3 | -1 (i=2) | 窗口满了，但队首下标1 >= 0，未过期 | 队尾 3 < -1？否（3大于-1） | [ 3(1), -1(2) ] | 输出 3✅ |
| 4 | -3 (i=3) | 窗口范围 [1,3]，队首1未过期 | 队尾 -1 < -3？否 | [ 3(1), -1(2), -3(3) ] | 输出 3✅ |
| 5 | 5 (i=4) | 窗口范围 [2,4]，队首下标1 < 2，过期！弹出3 | 队尾 -3<5弹；-1<5弹；3<5弹 | [ 5(4) ] | 输出 5✅ |
| 6 | 3 (i=5) | 窗口范围 [3,5]，队首4未过期 | 队尾 5 < 3？否 | [ 5(4), 3(5) ] | 输出 5✅ |
| 7 | 6 (i=6) | 窗口范围 [4,6]，队首4未过期 | 队尾 3<6弹；5<6弹 | [ 6(6) ] | 输出 6✅ |
| 8 | 7 (i=7) | 窗口范围 [5,7]，队首6未过期 | 队尾 6<7弹 | [ 7(7) ] | 输出 7✅ |
一、我们到底在维护什么？（先看数据结构）
我们用一个双端队列（deque），里面只存数组下标（不存数值）。
队列的绝对规则（铁律）：
从队首到队尾，这些下标对应的数值必须严格递减。
（例如：队首是10，队尾是3，中间是7，即 10 > 7 > 3）
二、每次窗口移动，只做这三步（死记硬背）
假设当前遍历到下标i，窗口范围是[i - k + 1, i]。
第1步（清理过期）：
如果队首的下标小于i - k + 1（即这个下标已经不在当前窗口里了），就把队首从左边弹出去。
第2步（清理弱者）：
只要队尾对应的数值小于等于nums[i]（新来的数），就把队尾从右边弹出去。（因为新来的数比你大，还比你晚过期，你永远没机会当最大值了）例如1 3 [-1 -3 5] 3 6 7
第3步（新王入队）：
把当前下标i从队尾放进去。
做完这三步，队首下标对应的数值，就是当前窗口的最大值。
代码还没写。
)
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
