企业官网建设流程全解析

力扣题目链接

此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

第一层：暴力法为什么不行？（你的想法）

你说的“直接比较每k个数字里最大的”叫暴力滑动。
假设数组长度n=100000，窗口大小k=50000。
每滑动一次，你就要比较 50000 次，一共要滑动 50001 次。总计算量是 25亿次，绝对超时。

第二层：单调队列到底在干嘛？（核心思想）

单调队列不是在“找最大值”，而是在维护一个“最大值候选人”的名单，并且按出场顺序排好队。

关键洞察：当窗口滑动时，一个新元素进来了。如果这个新元素比队列里末尾的某些旧元素还大，那么那些旧元素就永远不可能成为最大值了（因为它们比新元素小，而且还比新元素先过期）。所以，直接把那些没用的旧元素从队尾踢出去。

这就是“单调递减队列”名字的由来——队列里从头到尾，数值越来越小。

第三层：为什么不需要精确弹出“被移除的那个元素”？（解决你的最大疑问）

你问：“已经排序之后的队列，怎么能把窗口要移除的元素弹出呢？”

答案是：我们根本不关心它是不是在队列里，我们只在它“恰好是队首”时才弹出它。

请看下面这个活生生的例子，你就全明白了：
数组[5, 3, 4, 1]，窗口k=3。

1. 窗口 [5, 3, 4]：

   • 5 进队：[5]

   • 3 进队：[5, 3]（比5小，留着备用）

   • 4 进队：发现队尾的3比4小，把3踢掉（因为3没4大，还比4先过期，永无出头之日）。队里变成[5, 4]。

   • 最大值= 队首5。

2. 窗口滑动，移除 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。
队列里存的是下标（方便判断过期），为了你看得懂，我写成值(下标)。

一、我们到底在维护什么？（先看数据结构）

我们用一个双端队列（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从队尾放进去。

做完这三步，队首下标对应的数值，就是当前窗口的最大值。

代码还没写。