← 滑动窗口 · Sliding Window / 双端单调队列：及时舍弃「不可能成为最大值」的数 待审核 3 / 7

Monotonic Deque · 核心

双端单调队列：及时舍弃「不可能成为最大值」的数

本页解决窗内取最值一页留下的重复比较问题。核心性质：扫到 nums[i] 时，它前面那些比它小、又比它早进窗的数，不可能再成为后续任何窗口的最大值——因为只要它们还在窗里，更大的 nums[i] 也在，而且 nums[i] 在窗口中停留得更久。这些数不再有用，可以从队尾弹出。

维护一个双端队列 Q，里面存的是下标，且对应的值从队首到队尾单调递减。每个 i 做三件事：

其一、队尾淘汰——只要 $nums[i] \ge nums[Q.back]$ 就把队尾弹出（它不可能再胜过 i），直到队尾比 i 大，再把 i 入队尾；
其二、队首过期——若队首下标已滑出窗口 ( $i - Q.front() + 1 > k$ )，从前端弹出；
其三、记录结果——当 $i \ge k-1$ 窗口填满，nums[Q.front] 就是当前窗口最大值。

1 · 为什么是 $O(n)$ ?

这个 while 并不会让每个 i 都执行 k 次。用均摊分析计数：每个下标只会进队一次、出队一次（要么被某个更大的后来者从队尾弹出，要么因滑出窗口从队首离开）。n 个下标 → 总入队 + 出队操作 $\le 2n$ 次，所以整趟遍历是均摊 $O(n)$ ，明显优于暴力的 $O(n\cdot k)$ 。空间 $O(k)$ （队列里下标都在一个窗口内）。

队首为什么一定是最大值？队列对应的值单调递减，所以 front 的值最大；又因为每次都把过期（滑出窗口）的 front 弹掉，留在队里的下标全都仍在当前窗口内——队首既最大、又在窗内，自然就是窗口最大值。把代码里的 $\ge$ 改成 $\le$ 、front 取最小，就变成滑动窗口最小值。定长取最值还有另一条预处理路线，见分块法。