单调队列解决滑动窗口极值双端队列在 O(N) 复杂度下的单调性维护技巧在海量流式数据监控、高并发指标统计如最近 5 分钟接口最大响应耗时以及动态规划状态加速中“滑动窗口极值”是一个出现频次极高的高频问题。在面试或算法竞赛中很多人拿到这类题目第一时间会想到大顶堆优先队列PriorityQueue。堆虽然能以 $O(\log k)$ 维护极值但它存在两个致命痛点第一在窗口右移时滑出窗口的元素可能并不在堆顶需要引入“延迟删除”或额外维护哈希表做堆内元素寻址逻辑极其臃肿第二在千万级流式计算场景下每一个数据点都触发 $\log k$ 次树形调整CPU Cache 命中率极差。真正达到理论极限解法的是单调队列Monotonic Queue——借助双端队列Deque以均摊严格 $O(N)$ 的时间复杂度和 $O(k)$ 的空间复杂度行云流水地完成动态极值维护。单调队列的哲学既生瑜何生亮单调队列的核心逻辑可以用一句通俗的话来概括“如果一个选手比你年轻还比你强那你就永远没有出头之日了。”假设我们要求解的是滑动窗口内的最大值设当前窗口正在向右移动新元素从右侧进入窗口。此时在队列中已经存在若干比新元素更早进入的老元素。如果某个老元素的数值小于或等于新进来的元素那么无论窗口接下来怎么往右滑动老元素一定会比新元素先出窗它的生命周期更短在老元素存活的整个区间内新元素都在且新元素的数值更大。这意味着这个老元素在未来的任何时刻都绝无可能成为窗口内的最大值。它的存在对求解极值没有任何意义。因此在将新元素推入队列前必须从**队尾back**将所有比它小或相等的元素全部暴力剔除。graph LR subgraph Deque维护过程 direction LR Head[队头: 存活的最大值下标] -- Mid[...] Mid -- Tail[队尾: 候选较小值] end New[新元素到来] --|从队尾比较| Tail Tail --|数值 新元素| PopBack[队尾出队 淘汰] New --|直至队尾 新元素| PushBack[新元素下标压入队尾] Head --|下标超出窗口左边界| PopFront[队头出队 过期]致命细节辨析为什么必须存下标而非元素值很多初学者在手撕单调队列时总想当然地在双端队列里直接存nums[i]的值结果往往在“处理元素滑出窗口”时陷入泥潭// 典型错误尝试队列直接存值 std::dequeint q; // 遍历到 i 时试图出窗 nums[i - k] if (!q.empty() q.front() nums[i - k]) { q.pop_front(); }这种写法在窗口内存在重复数值时会引发灾难性的逻辑崩溃。例如数组为[3, 3, 2, 1]窗口大小 $k 3$初始入队两个3如果队列维护严格递减在第二个3入队时误将第一个3弹出当窗口右移需要淘汰首个3时直接误把第二个仍在窗口内的3给淘汰掉了。铁律单调队列必须存储数组下标Index存下标具有两大不可替代的优势天然绑定生命周期根据当前索引i和队头下标q.front()只需一行判断q.front() i - k或 i - k 1即可瞬间得知队头元素是否已滑出窗口范围彻底与重复数值解耦。$O(1)$ 获取元素值通过nums[q.front()]可以随时随地以 $O(1)$ 时间获取当前窗口的最大值。维护单调性的边界选择严格还是非严格在从队尾淘汰元素时判断条件究竟是nums[q.back()] nums[i]还是nums[q.back()] nums[i]答案是必须使用非严格单调递减看一个微型测试场景当前窗口新进来的元素与队尾元素相等nums[q.back()] nums[i]。前面的那个元素下标更靠前意味着它会更早滑出窗口新进来的元素下标更靠后生命力更持久既然两者数值完全相同那么更老的那个元素完全没有任何继续驻留的价值。使用将相等的老元素从队尾弹出不仅在数学上完全等价而且能极致压缩双端队列的实际物理长度避免无谓的内存开销与冗余遍历。工业级高效模板实现下面分别给出 C 与 Java 21 的高性能标准实现。代码结构经过精心打磨杜绝一切冗余分支。1. 现代 C 实现LeetCode 239 标准范式#include vector #include deque class MonotonicQueueSolver { public: std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { int n nums.size(); if (n 0 || k 0) return {}; std::vectorint result; result.reserve(n - k 1); // 预分配内存杜绝动态扩容重哈希 std::dequeint dq; // 存储数组下标 for (int i 0; i n; i) { // 1. 队头生命周期检查如果队头下标已滑出窗口范围 [i - k 1, i]出队头 if (!dq.empty() dq.front() i - k) { dq.pop_front(); } // 2. 队尾单调性维护淘汰所有数值小于或等于当前元素的老元素 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 3. 当前下标入队尾 dq.push_back(i); // 4. 窗口成型长度达到 k后队头即为当前窗口的最大值 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };2. Java 实现基于原生数组模拟循环队列的终极性能优化在 Java 中标准库的java.util.ArrayDeque已经非常高效但在极其苛刻的高频交易或超大规模流式场景下使用原生一维数组手写双端队列可以彻底消灭对象封装与包装类型拆装箱开销public class FastMonotonicQueue { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return new int[0]; } int n nums.length; int[] result new int[n - k 1]; int[] deque new int[n]; // 数组模拟双端队列存放下标 int head 0; // 队头指针 int tail 0; // 队尾指针 (开区间指向下一个可插入位置) for (int i 0; i n; i) { // 1. 出窗校验 if (head tail deque[head] i - k) { head; } // 2. 维护单调递减 while (head tail nums[deque[tail - 1]] nums[i]) { tail--; } // 3. 压入新下标 deque[tail] i; // 4. 收集极值 if (i k - 1) { result[i - k 1] nums[deque[head]]; } } return result; } }复杂度证明为什么是严格的 O(N)很多初学者看到代码外层有一个for循环内层还有一个while循环下意识地认为时间复杂度是 $O(N \times k)$。这种直觉是错误的。证明算法复杂度必须采用摊还分析Amortized Analysis整个算法运行期间数组中的每一个下标 $i$从 $0$ 到 $n-1$恰好只会被push_back进队列一次。队列中的每一个元素要么在队尾维护单调性时被pop_back弹出要么在队头过期时被pop_front弹出一旦弹出便永远不会再次入队。因此整个执行生命周期内所有入队操作总次数为 $N$所有出队操作总次数上限为 $N$。总的时间复杂度严格为$$\mathcal{O}(N N) \mathcal{O}(N)$$均摊到每一个滑动步骤上处理新元素的时间复杂度仅为 $\mathcal{O}(1)$。空间复杂度在最坏情况下队列长度不会超过 $k$为 $\mathcal{O}(k)$。进阶应用场景从基础滑动窗口到 DP 状态加速单调队列的威力绝不仅限于滑动窗口本身它更是一把斩断高阶动态规划复杂度维度的利剑。1. 多重背包问题单调队列优化在经典多重背包中朴素 DP 复杂度为 $\mathcal{O}(V \sum C_i)$即便进行二进制拆分也是 $\mathcal{O}(V \sum \log C_i)$。通过将状态按体积余数 $r j \pmod w$ 进行分组状态转移方程转化为$$dp[r p \cdot w] \max_{p - c \le q \le p} { dp[r q \cdot w] - q \cdot v } p \cdot v$$这本质上就是一个标准的一维滑动窗口求最值模型。借助单调队列可将多重背包的复杂度彻底压制到不可思议的 $\mathcal{O}(N \times V)$。2. 子数组长度受限的最大连续和如本文在评测小参数大模型时提到的那道题目求长度不超过 $k$ 的最大连续子数组和。利用前缀和转换求 $\max(P[i] - P[j])$ 满足 $i - k \le j i$。这等价于在滑动的 $[i - k, i - 1]$ 范围内动态查询最小的 $P[j]$。使用单调队列维护递增的前缀和下标同样能在 $\mathcal{O}(N)$ 内完成秒杀。总结单调队列是计算机科学中“以空间换时间”、“以淘汰策略换极致检索性能”的经典缩影。掌握它的核心不在于背诵模板代码而在于深刻理解以下三点淘汰劣解的即时性通过逆序遍历队尾主动放弃毫无希望的次优解下标绑定的确定性用下标代替数值作为队列承载体赋予单调队列精准的生命周期管理能力摊还分析的恒定性每个元素一生进出各一次换来的是面对海量流数据时从容不迫的坚韧性能。