单调队列（Monotonic Queue）的原理与应用

字数 2707 2025-12-12 17:14:43

单调队列（Monotonic Queue）的原理与应用

单调队列是一种特殊的队列结构，它能够在 O(1) 的平均时间内获取队列中的最大值或最小值，常用于解决滑动窗口的最值问题。它与单调栈类似，但允许从队列的两端（队头和队尾）进行操作。

一、什么是单调队列？

单调队列的核心思想是维护一个具有单调性的双端队列。这个队列中的元素（通常是元素的下标）满足某种单调性（递增或递减），并且能快速获取窗口中的最值。我们以维护一个“递减单调队列”来获取滑动窗口的最大值为例进行讲解。

数据结构基础：

一个标准的双端队列（deque），可以从队头和队尾插入或删除元素。
队列中存储的通常是元素在原数组中的下标，这样可以方便地判断元素是否还在当前窗口内。

二、单调队列的工作过程（以滑动窗口最大值为例）

假设给定一个数组 nums 和窗口大小 k，我们需要返回每个大小为 k 的窗口中的最大值。

示例：
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

目标是得到结果：[3, 3, 5, 5, 6, 7]。

步骤分解：

初始化：
- 创建一个空的双端队列 deque，用来存储元素的下标。
- 结果列表 result 为空。
遍历数组，处理每个元素（索引为 i）：
- 我们将每个元素 nums[i] 视为要“进入”窗口的新元素。
维护单调递减队列：
- 在插入新元素的下标 i 之前，需要确保队列的单调性（递减）。
- 操作：从队尾开始，不断移除比 nums[i] 小的元素的下标，直到队列为空或队尾元素对应的值大于等于 nums[i]。
- 为什么？因为如果队列中已有元素比新元素小，那么在新元素存在的情况下，这些较小的元素永远不可能成为窗口的最大值（窗口向右滑动，新元素会存在更久），所以可以直接丢弃它们。
- 然后将下标 i 加入队尾。
移除超出窗口的元素：
- 检查队头元素（下标）是否已经超出了当前窗口的范围。当前窗口的范围是 [i - k + 1, i]。
- 如果队头下标 <= i - k（严格小于窗口左边界），说明它已经不在窗口内，从队头弹出。
记录窗口最大值：
- 当 i >= k - 1 时，说明窗口已经形成（从索引0开始，窗口在 i=2 时第一次形成）。
- 此时，队头元素对应的值就是当前窗口的最大值，将其加入结果列表。

结合示例的逐步推演：

i=0, nums[0]=1, deque=[] -> 队尾插入0，deque=[0]，i<2，不记录。
i=1, nums[1]=3, deque=[0]: 队尾值nums[0]=1<3，弹出0 -> deque=[]，插入1 -> deque=[1]，i<2，不记录。
i=2, nums[2]=-1, deque=[1]: 队尾值nums[1]=3 > -1，直接插入 -> deque=[1,2]。i>=2，记录nums[deque[0]]=3 -> result=[3]。
i=3, nums[3]=-3, deque=[1,2]: 队尾值nums[2]=-1 > -3，直接插入 -> deque=[1,2,3]。移除队头？deque[0]=1, i-k=0, 1>0，保留。记录nums[1]=3 -> result=[3,3]。
i=4, nums[4]=5, deque=[1,2,3]: 从队尾开始，nums[3]=-3<5，弹出3；nums[2]=-1<5，弹出2；nums[1]=3<5，弹出1 -> deque=[]，插入4 -> deque=[4]。移除队头？4>1，保留。记录nums[4]=5 -> result=[3,3,5]。
i=5, nums[5]=3, deque=[4]: 队尾值nums[4]=5>3，直接插入 -> deque=[4,5]。移除队头？4>2，保留。记录nums[4]=5 -> result=[3,3,5,5]。
i=6, nums[6]=6, deque=[4,5]: 从队尾开始，nums[5]=3<6，弹出5；nums[4]=5<6，弹出4 -> deque=[]，插入6 -> deque=[6]。移除队头？6>3，保留。记录nums[6]=6 -> result=[3,3,5,5,6]。
i=7, nums[7]=7, deque=[6]: 从队尾开始，nums[6]=6<7，弹出6 -> deque=[]，插入7 -> deque=[7]。移除队头？7>4，保留。记录nums[7]=7 -> result=[3,3,5,5,6,7]。

结果与预期一致。

三、单调队列的性质总结

时间复杂度：每个元素最多入队一次、出队一次，因此处理 n 个元素的总时间复杂度为 O(n)。
空间复杂度：队列中最多存储 k 个元素（通常更少），为 O(k)。
单调性方向：
- 若要维护窗口最大值，则保持队列递减（队头最大）。
- 若要维护窗口最小值，则保持队列递增（队头最小）。

四、单调队列的典型应用场景

经典的滑动窗口最大值/最小值问题（如上所述）。
带限制的子数组最值问题：例如，在满足某些条件的子数组中求最值，窗口大小可变但受限。
优化动态规划：某些 DP 的状态转移方程形式为 dp[i] = min/max(dp[j] + f(i, j))，其中 j 在一个滑动窗口内，可以用单调队列将转移复杂度从 O(nk) 降到 O(n)。一个著名例子是“限制长度的最大子段和”问题。
辅助其他数据结构：在某些复杂的流数据处理中，可以结合单调队列来实时维护最值。

五、与单调栈的区别

特性	单调栈	单调队列
操作端	仅一端（栈顶）插入删除	两端（队头、队尾）都可以操作
典型用途	寻找下一个更大/更小元素	滑动窗口的最值
元素过期	无过期概念，元素永久存在	元素会因离开窗口而“过期”
维护重点	维护结构整体的单调性	维护单调性，并处理过期元素

简单来说，单调队列是滑动窗口问题的利器，其核心在于通过剔除不可能成为答案的元素，并用双端队列维护一个具有单调性的候选值序列，从而在 O(1) 级别的时间获取当前窗口的最值。

单调队列（Monotonic Queue）的原理与应用单调队列是一种特殊的队列结构，它能够在 O(1) 的平均时间内获取队列中的最大值或最小值，常用于解决滑动窗口的最值问题。它与单调栈类似，但允许从队列的两端（队头和队尾）进行操作。一、什么是单调队列？单调队列的核心思想是维护一个具有单调性的双端队列。这个队列中的元素（通常是元素的下标）满足某种单调性（递增或递减），并且能快速获取窗口中的最值。我们以维护一个“递减单调队列”来获取滑动窗口的最大值为例进行讲解。数据结构基础：一个标准的双端队列（deque），可以从队头和队尾插入或删除元素。队列中存储的通常是元素在原数组中的下标，这样可以方便地判断元素是否还在当前窗口内。二、单调队列的工作过程（以滑动窗口最大值为例）假设给定一个数组 nums 和窗口大小 k ，我们需要返回每个大小为 k 的窗口中的最大值。示例： nums = [1, 3, -1, -3, 5, 3, 6, 7] , k = 3 目标是得到结果： [3, 3, 5, 5, 6, 7] 。步骤分解：初始化：创建一个空的双端队列 deque ，用来存储元素的下标。结果列表 result 为空。遍历数组，处理每个元素（索引为 i ）：我们将每个元素 nums[i] 视为要“进入”窗口的新元素。维护单调递减队列：在插入新元素的下标 i 之前，需要确保队列的单调性（递减）。操作：从队尾开始，不断移除比 nums[i] 小的元素的下标，直到队列为空或队尾元素对应的值大于等于 nums[i] 。为什么？因为如果队列中已有元素比新元素小，那么在新元素存在的情况下，这些较小的元素永远不可能成为窗口的最大值（窗口向右滑动，新元素会存在更久），所以可以直接丢弃它们。然后将下标 i 加入队尾。移除超出窗口的元素：检查队头元素（下标）是否已经超出了当前窗口的范围。当前窗口的范围是 [i - k + 1, i] 。如果队头下标 <= i - k （严格小于窗口左边界），说明它已经不在窗口内，从队头弹出。记录窗口最大值：当 i >= k - 1 时，说明窗口已经形成（从索引0开始，窗口在 i=2 时第一次形成）。此时，队头元素对应的值就是当前窗口的最大值，将其加入结果列表。结合示例的逐步推演： i=0, nums[ 0]=1, deque=[] -> 队尾插入0，deque=[ 0]，i <2，不记录。 i=1, nums[ 1]=3, deque=[ 0]: 队尾值nums[ 0]=1<3，弹出0 -> deque=[]，插入1 -> deque=[ 1]，i <2，不记录。 i=2, nums[ 2]=-1, deque=[ 1]: 队尾值nums[ 1]=3 > -1，直接插入 -> deque=[ 1,2]。i>=2，记录nums[ deque[ 0]]=3 -> result=[ 3 ]。 i=3, nums[ 3]=-3, deque=[ 1,2]: 队尾值nums[ 2]=-1 > -3，直接插入 -> deque=[ 1,2,3]。移除队头？deque[ 0]=1, i-k=0, 1>0，保留。记录nums[ 1]=3 -> result=[ 3,3 ]。 i=4, nums[ 4]=5, deque=[ 1,2,3]: 从队尾开始，nums[ 3]=-3<5，弹出3；nums[ 2]=-1<5，弹出2；nums[ 1]=3<5，弹出1 -> deque=[]，插入4 -> deque=[ 4]。移除队头？4>1，保留。记录nums[ 4]=5 -> result=[ 3,3,5 ]。 i=5, nums[ 5]=3, deque=[ 4]: 队尾值nums[ 4]=5>3，直接插入 -> deque=[ 4,5]。移除队头？4>2，保留。记录nums[ 4]=5 -> result=[ 3,3,5,5 ]。 i=6, nums[ 6]=6, deque=[ 4,5]: 从队尾开始，nums[ 5]=3<6，弹出5；nums[ 4]=5<6，弹出4 -> deque=[]，插入6 -> deque=[ 6]。移除队头？6>3，保留。记录nums[ 6]=6 -> result=[ 3,3,5,5,6 ]。 i=7, nums[ 7]=7, deque=[ 6]: 从队尾开始，nums[ 6]=6<7，弹出6 -> deque=[]，插入7 -> deque=[ 7]。移除队头？7>4，保留。记录nums[ 7]=7 -> result=[ 3,3,5,5,6,7 ]。结果与预期一致。三、单调队列的性质总结时间复杂度：每个元素最多入队一次、出队一次，因此处理 n 个元素的总时间复杂度为 O(n) 。空间复杂度：队列中最多存储 k 个元素（通常更少），为 O(k) 。单调性方向：若要维护窗口最大值，则保持队列递减（队头最大）。若要维护窗口最小值，则保持队列递增（队头最小）。四、单调队列的典型应用场景经典的滑动窗口最大值/最小值问题（如上所述）。带限制的子数组最值问题：例如，在满足某些条件的子数组中求最值，窗口大小可变但受限。优化动态规划：某些 DP 的状态转移方程形式为 dp[i] = min/max(dp[j] + f(i, j)) ，其中 j 在一个滑动窗口内，可以用单调队列将转移复杂度从 O(nk) 降到 O(n)。一个著名例子是“ 限制长度的最大子段和 ”问题。辅助其他数据结构：在某些复杂的流数据处理中，可以结合单调队列来实时维护最值。五、与单调栈的区别 | 特性 | 单调栈 | 单调队列 | | :--- | :--- | :--- | | 操作端 | 仅一端（栈顶）插入删除 | 两端（队头、队尾）都可以操作 | | 典型用途 | 寻找下一个更大/更小元素 | 滑动窗口的最值 | | 元素过期 | 无过期概念，元素永久存在 | 元素会因离开窗口而“过期” | | 维护重点 | 维护结构整体的单调性 | 维护单调性，并处理过期元素 | 简单来说，单调队列是滑动窗口问题的利器，其核心在于通过剔除不可能成为答案的元素，并用双端队列维护一个具有单调性的候选值序列，从而在 O(1) 级别的时间获取当前窗口的最值。