#创作计划# 单调队列

AAA逃离森林湖的蔡锡龙批发

2026-04-11 14:42:17

发布于：广东

9阅读

0回复

0点赞

字数，使用Microsoft Word统计，以字符（带空格）为准：
版本1(26-04-11 14:15)：原文2659字，渲染后2541字。
版本2(26-04-11 14:42 更新一道例题)：原文3373，渲染3189。

前言

https://www.acgo.cn/application/2042830309581336576 宣团。

正文

什么是单调队列？

顾名思义，单调队列的重点分为「单调」和「队列」．
「单调」指的是元素的「规律」——递增（或递减）．
「队列」指的是元素只能从队头和队尾进行操作．
Ps. 单调队列中的 "队列" 与正常的队列有一定的区别，稍后会提到
——OI Wiki https://oi-wiki.org/ds/monotonous-queue/

让我们解释一下。

「单调」指的是元素的「规律」——递增（或递减）：简单来说，单调队列维护一段区间内的极值——最大值或者最小值。
当维护区间最大值时，队列元素递减；维护最小值时递增。
「队列」指的是元素只能从队头和队尾进行操作：涉及双端「队列」的操作只有：查询队列头/尾，队列头/尾弹出，队列尾插入。
Ps. 单调队列中的 "队列" 与正常的队列有一定的区别，稍后会提到：由于这里的队列需要同时进行头尾的插入/删除，所以需要一种特殊的队列：
双端队列。

单调

假设我们要维护区间的最大值，那么我们就要构造一个递减的单调队列。

考虑有相等的元素，实际上是不递增。

为什么？
因为：如果当前元素大于队尾元素，那么显然队尾元素不再能成为最大值。所以这个队列一定满足：
对于任何一个前面有一元素的元素，这个元素一定不大于它前面的元素。
也就是递减。
此时队头就是最大值。
如果维护最小值，那么构造的就是递增的单调队列。相应的，队头就是最小值。

队列

这个部分不用过多解释。关于单调队列的所有操作都只需要在头/尾进行。

双端队列

双端队列有两种实现方式：数组模拟双端队列 / STL std::deque<>。
这里选择 STL 的双端队列，关于数组模拟的双端队列可以参考 OI-Wiki的数组模拟部分实现，对于双端的特殊部分只需要交换左右指针然后调一下增减。这里不做特殊说明。

STL 的时间复杂度有时较高。

实现

以此题为例：https://www.acgo.cn/problemset/info/22744

这题洛谷上是黄题。洛谷原题：https://www.luogu.com.cn/problem/P1886

思路

先考虑最大值。
通过前面的“单调”部分，我们知道要维护区间最大值则应该构建递减单调队列。
那么怎么构建呢？很简单，当队尾元素小于当前要插入的元素就直接pop_back()，直到队尾大于当前元素。
还要注意一点，就是当队头滑出了窗口则不能作为答案。
对于每一元素，步骤如下：

当队列不为空且当前队头元素已经滑出窗口，弹出队头；
当队列不空且当前队尾元素小于当前元素，弹出队尾；
插入当前元素；
如果满足输出条件，输出当前队头。

若处理最小值，则将第二步的“大于”替换为“小于”，构建的就是一个递增的单调队列。

小技巧：得益于优化，当&&连接的两个条件的第一个条件为假，则不会去运算第二个条件。所以可以把判不空和查询头/尾塞到一起。
还有这题要开long long。

处理最大值代码如下：

for(int i = 1;i <= n;i++){                                 //对于每一元素，步骤如下：
    while(dq.size() && dq.front() < i-k+1)dq.pop_front();  //1. 当队列不为空且当前队头元素已经滑出窗口，弹出队头；
    while(dq.size() && a[dq.back()] < a[i])dq.pop_back();  //2. 当队列不空且当前队尾元素*小于*当前元素，弹出队尾；
    dq.push_back(i);                                       //3. 插入当前元素；
    if(i>=k) cout << a[dq.front()] << ' ';                 //4. 如果满足输出条件，输出当前队头。
}

完整代码。记得在两个最大/最小之间清空。

//注：此代码不提供完整注释，核心注释见上。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[1145144];
deque<int> dq;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i =1 ;i <= n;i++) cin >> a[i];
    //min
    for(int i = 1;i <= n;i++){
        while(dq.size() && dq.front() < i-k+1)dq.pop_front();
        while(dq.size() && a[dq.back()] > a[i])dq.pop_back();
        dq.push_back(i);
        if(i>=k) cout << a[dq.front()] << ' ';
    }
    cout << endl;
    dq.clear();
    //max
    for(int i = 1;i <= n;i++){
        while(dq.size() && dq.front() < i-k+1)dq.pop_front();
        while(dq.size() && a[dq.back()] < a[i])dq.pop_back();
        dq.push_back(i);
        if(i>=k) cout << a[dq.front()] << ' ';
    }
}

另一道例题：

ACGO Ver ：https://www.acgo.cn/problemset/info/21345
至于为啥洛谷版本在前面是因为你Go的神秘问题导致洛谷的 AC Code 在 ACGO 上会炸出大量 RE，原因不明

这题也是类似的，注意这题的实际涉及到的位置是 $i-m$ 且不包含 $i$ （踩过坑，这题题面太糊了）。
还是一个板子。只是把插入元素放到后面。
此题无需long long。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[2145144];
deque<int> dq;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++){
        while(dq.size() && dq.front() < i-m)dq.pop_front();
        while(dq.size() && a[dq.back()] > a[i])dq.pop_back();
        if(i == 1) cout << 0 << endl;
        else cout << a[dq.front()] << endl;
        dq.push_back(i);
    }
}