[!info] related notes

单调队列

Overview

一、 它的本质是什么？

单调队列本质上是一个双端队列（Deque, Double-Ended Queue），但在普通的入队和出队操作之上，它给自己强加了一条极其严格的规矩：队列中的元素必须时刻保持单调递减（或单调递增）的顺序。

• 单调递减队列： 队首永远是当前最大的元素。用于求滑动窗口内的最大值。
• 单调递增队列： 队首永远是当前最小的元素。用于求滑动窗口内的最小值。

二、 它解决了什么核心问题？

它专门用于解决**“滑动窗口求最值”**的问题。

普通滑动窗口找最值需要每次重头遍历窗口内的元素，时间复杂度退化为 $O(N \times K)$（$N$ 为数组长度，$K$ 为窗口大小）。而单调队列通过巧妙地“淘汰废弃数据”，能将寻找当前窗口最值的时间压缩到平摊下来的 $O(1)$，整体算法时间复杂度降为完美的 $O(N)$。

三、 核心运作逻辑（残酷职场法则）

记忆单调队列最好的方式是引入“内卷职场”模型。队列相当于一个公司的核心骨干群：

• 数字的大小 = 员工的工作能力。
• 在原数组中的下标（索引） = 员工的年龄/入职时间（下标越大，越年轻）。

单调队列只维护两个核心动作：

1. 保持单调性：新员工入职（队尾入队 push）

当一个新元素准备从队尾进入时，它会和前面的老员工（队尾元素）进行比较。

如果新员工的“能力”（值）大于等于老员工，老员工就会立刻被“淘汰”（从队尾 pop 出去）。因为新员工既比你强，还比你年轻（在窗口里存活的时间更久），只要新员工在，老员工永远不可能成为公司最强（窗口最大值）。

这个动作会一直循环，直到遇到比新员工强的，或者队列空了为止，新员工才排入队尾。

2. 维护窗口范围：老员工退休（队首出队 shift）

每次窗口向前滑动（时间流逝），我们需要检查坐在“老大”位置（队首）的员工是否已经到达了法定退休年龄（其原始下标已经掉出了当前滑动窗口的范围）。

如果越界了，就必须让他强制退休（从队首 shift 出去）。

四、 代码实现的关键细节

• 存下标，不存值： 队列中实际存放的应该是原数组的索引（下标），而不是具体的值。因为我们需要通过下标来判断元素是否“过期（退休）”。要比较能力大小时，用 nums[队列里的下标] 即可。
• 双端操作： 因为需要在队尾“踢人”（维护单调性），又需要在队尾“加人”，还需要在队首“踢人”（维护窗口范围），所以必须使用双端队列。在 JavaScript/TypeScript 中，可以直接用 Array 配合 push()（尾部加）、pop()（尾部删）和 shift()（头部删）来模拟。

五、 时间复杂度为什么是 $O(N)$？

虽然代码里有一层 for 循环，里面还套了一个 while 循环（在队尾不断踢人），看起来像嵌套循环，但其实不是。

关键在于：每一个元素，在整个遍历过程中，最多只会被 push 进队列一次，也最多只会被 pop/shift 出队列一次。

所以，无论 while 循环内部踢人的动作发生得多频繁，所有进出队列的操作总次数不会超过 $2N$ 次。平摊到每一步，时间复杂度就是严格的 $O(N)$。

---

下一步建议：

数据结构界有一个和“单调队列”齐名的孪生兄弟，叫做单调栈 (Monotonic Stack)。它的核心思想也是“新老更替”，专门用来解决“寻找数组中每一个元素左边/右边第一个比它大/小的元素”这类问题（比如著名的力扣 739 题《每日温度》）。