单调队列（Monotonic Queue）

定义

单调队列是一种特殊的队列数据结构，其核心特征是：队列中的元素严格保持单调递增或单调递减的顺序。

与 单调栈 类似，单调队列通过维护序列的单调性，将某些非线性查询操作优化至线性时间复杂度。但不同的是，单调队列主要解决滑动窗口最值问题，而单调栈解决的是「最近更大/更小元素」问题。

核心思想

单调队列结合了队列的「先进先出」特性与单调性：

• 队列：保证元素进入和离开的顺序性（模拟滑动窗口）
• 单调性：保证队头元素始终是当前窗口的最大值或最小值

分类

类型	单调性	适用场景
单调递增队列	队头 → 队尾递增	滑动窗口最小值
单调递减队列	队头 → 队尾递减	滑动窗口最大值

经典问题：滑动窗口

问题描述

给定一个长度为 $n$ 的数组和一个窗口大小为 $k$ 的滑动窗口，从左到右滑动窗口，输出每个位置窗口内元素的最大值和最小值。

POJ 2823 是该问题的经典例题。¹

问题形式化

设数组 $A[\mathrm{1...}n]$，窗口大小为 $k$，求：

• $Min[i]=\min \{A[i],A[i+1],...,A[i+k-1]\}$，其中 $1\le i\le n-k+1$
• $Max[i]=\max \{A[i],A[i+1],...,A[i+k-1]\}$，其中 $1\le i\le n-k+1$

朴素算法

遍历所有窗口，对每个窗口扫描 $k$ 个元素，时间复杂度 $O(n\times k)$，当 $k$ 接近 $n$ 时复杂度高达 $O(n^2)$。

单调队列优化

核心思想：每个元素最多入队一次、出队一次，总时间复杂度 $O(n)$。

算法详解

维护单调递减队列（求窗口最大值）

以维护单调递减队列为例，求滑动窗口最大值。设当前遍历到下标 $i$，队列 $Q$ 存储数组下标（注意是下标而非元素值）。

入队操作：

1. 若队列为空，直接将 $i$ 入队
2. 若 $A[i]\le A[Q_{tail}]$：由于我们维护递减队列，直接将 $i$ 入队至队尾
3. 若 $A[i]>A[Q_{tail}]$：$A[i]$ 比队尾元素更大，弹出队尾（因为这些元素永远不可能成为窗口最大值），重复此过程直到队列为空或 $A[i]\le A[Q_{tail}]$，再将 $i$ 入队

出队操作：

• 队头的下标如果已经不在当前窗口内（即 $Q_{head}\le i-k$），则将其弹出

取答案：

• 窗口形成后（$i\ge k$），队头元素 $Q_{head}$ 就是当前窗口最大值的下标

手动模拟

给定数组 $A=[1,3,-1,-3,5,3,6,7]$，$k=3$，求滑动窗口最大值。

步骤	$i$	$A[i]$	队列状态（下标）	窗口	最大值
1	0	1	[0]	[1]	-
2	1	3	[1]（弹出0）	[1,3]	-
3	2	-1	[1,2]	[1,3,-1]	3
4	3	-3	[2,3]（弹出1，-1>-3保留）	[3,-1,-3]	-1
5	4	5	[4]（弹出3,2）	[-1,-3,5]	5
6	5	3	[4,5]	[5,3]	5
7	6	6	[6]（弹出5,4）	[3,6]	6
8	7	7	[7]（弹出6）	[6,7]	7

输出最大值序列：$[3,3,5,5,6,7]$

关键性质

1. 元素只入队一次：每个下标 $i$ 被加入队列后就不会再次出现
2. 元素最多出队一次：每个下标最多被弹出一次
3. 均摊 $O(1)$：总入队次数 $=n$，总出队次数 $=n$，故总时间 $O(n)$
4. 下标有效性判断：通过比较下标值判断元素是否仍在窗口内

C++ 实现

求滑动窗口最大值（单调递减队列）

#include <bits/stdc++.h>
using namespace std;
 
vector<int> slidingWindowMax(const vector<int>& A, int k) {
    int n = A.size();
    vector<int> res;
    deque<int> q;  // 存储下标
    
    for (int i = 0; i < n; ++i) {
        // 维护单调递减队列：弹出比当前元素小的元素
        while (!q.empty() && A[i] >= A[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        
        // 弹出不在窗口内的元素
        if (q.front() <= i - k) {
            q.pop_front();
        }
        
        // 窗口形成后记录答案
        if (i >= k - 1) {
            res.push_back(A[q.front()]);
        }
    }
    return res;
}

求滑动窗口最小值（单调递增队列）

只需将比较符号反转：

vector<int> slidingWindowMin(const vector<int>& A, int k) {
    int n = A.size();
    vector<int> res;
    deque<int> q;  // 存储下标
    
    for (int i = 0; i < n; ++i) {
        // 维护单调递增队列：弹出比当前元素大的元素
        while (!q.empty() && A[i] <= A[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
        
        // 弹出不在窗口内的元素
        if (q.front() <= i - k) {
            q.pop_front();
        }
        
        // 窗口形成后记录答案
        if (i >= k - 1) {
            res.push_back(A[q.front()]);
        }
    }
    return res;
}

完整示例（POJ 2823 风格）

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    // 求最小值：单调递增队列
    deque<int> qMin;
    vector<int> ansMin;
    for (int i = 0; i < n; ++i) {
        while (!qMin.empty() && A[i] <= A[qMin.back()]) {
            qMin.pop_back();
        }
        qMin.push_back(i);
        if (qMin.front() <= i - k) qMin.pop_front();
        if (i >= k - 1) ansMin.push_back(A[qMin.front()]);
    }
    
    // 求最大值：单调递减队列
    deque<int> qMax;
    vector<int> ansMax;
    for (int i = 0; i < n; ++i) {
        while (!qMax.empty() && A[i] >= A[qMax.back()]) {
            qMax.pop_back();
        }
        qMax.push_back(i);
        if (qMax.front() <= i - k) qMax.pop_front();
        if (i >= k - 1) ansMax.push_back(A[qMax.front()]);
    }
    
    // 输出
    for (int i = 0; i < ansMin.size(); ++i) {
        if (i) cout << ' ';
        cout << ansMin[i];
    }
    cout << '\n';
    for (int i = 0; i < ansMax.size(); ++i) {
        if (i) cout << ' ';
        cout << ansMax[i];
    }
    cout << '\n';
    
    return 0;
}

复杂度分析

时间复杂度

操作	说明	时间复杂度
单次入队	最多一次	$O(1)$
单次出队	最多一次	$O(1)$
总时间	$n$ 个元素	$O(n)$

关键：每个元素最多入队一次、出队一次，整体操作次数为 $2n$，故时间复杂度 $O(n)$。

空间复杂度

队列最多存储 $k$ 个元素（下标），空间复杂度 $O(k)$，最坏情况下（窗口大小等于数组长度）为 $O(n)$。

与堆的对比

数据结构	滑动窗口最值	时间复杂度	空间复杂度
朴素算法	-	$O(nk)$	$O(1)$
单调队列	-	$O(n)$	$O(k)$
堆（维护k个元素）	-	$O(n\log k)$	$O(k)$

堆的方法：维护一个大小为 $k$ 的堆，每次取堆顶需要 $O(1)$，但插入删除需要 $O(\log k)$，总体 $O(n\log k)$。单调队列更优。

应用场景

滑动窗口类问题

• 滑动窗口最大值/最小值
• 流量控制、限流算法
• 股票价格区间统计

优化技巧

单调队列常用于优化动态规划：

• DP 优化：当 DP 转移方程具有单调性时，可用单调队列优化
• RMQ 问题：区间最值查询可结合 线段树 或稀疏表解决

总结

单调队列是处理滑动窗口最值问题的利器。其核心思想在于：

1. 队列：保证元素的进入和离开顺序，模拟滑动窗口的移动
2. 单调性：保证队头始终是当前窗口极值
3. 均摊分析：每个元素最多入队一次、出队一次，总时间 $O(n)$

单调队列与 堆、单调栈一样，都是竞赛和工程中常用的 $O(n)$ 复杂度数据结构。

参考资料

Footnotes

1. 本题来自 POJ 2823 Sliding Window，参见 POJ 2823 - Sliding Window ↩