#创作计划# 单调队列
2025-02-08 13:42:45
发布于：浙江
387阅读
0回复
0点赞
应@张子渝需求，现更新一篇单调栈和单调队列。（本篇只讲单调队列）
所谓单调就是指元素按递增或递减的排列方式规整地排列。
例如
{}，
{}，
{}...
都属于按单调排列，而
{}，
{}，
{}...
则不属于按单调排列。
单调队列
何为单调队列？顾名思义，单调队列即满足单调性的队列结构。为了方便描述，接下来以从队首到队尾满足递增的单调队列（即单调递增队列）举例。
现有一个单调队列，里面没有任何元素。
然后我把元素 加入队列，因为 {} 符合递增关系，所以可以直接加入队列。
接着再把元素 加入队列，因为 {} 仍符合递增关系，所以依旧可以直接加入队列。
可当如果我还要把元素 加入队列，因为 {} 不符合递增关系，那么就不可以直接加入队列。为保证队列的单调性，需先把元素 {} 依次弹出，再把元素 加入队列。
另外如果我们要弹出元素，考虑到同单调栈一样无论怎么弹，队列始终保持单调性（此处读者可自行理解），所以可直接弹出。
综上所述，单调队列基本代码应是这样的：
queue<int>q;
void pop(){
q.pop();//直接弹出
}
void push(int x){
while(q.size()&&q.back()>x) pop();
//当发现有队尾比x大时，就会一直把队列弹空，因为每次只能从队首弹，想弹出队尾，只能把队列弹空
q.push(x);
}
1.例题 求区间所有后缀最大值的位置
题目入口
该题是模板，今后注意到像“区间极值”一类的问题，可以考虑到单调队列。
该题 AC 代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long//扶苏的题通常都会卡ull
deque<int>q;
int n,k,a[1000010];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];//输入
if(i>k && q.front()==i-k) q.pop_front();//过期删除，也叫延迟删除
while(!q.empty() && a[i]>=a[q.back()]) q.pop_back();
q.push_back(i);//模板操作
if(i>=k)cout<<q.size()<<"\n";//输出
}
return 0;
}
此处细心的读者可能已经发现我单调队列用的 STL 是 deque，不是 queue，那么我就借此篇讲讲 deque（双端队列），也顺便给那个讲 map 加精的人找个工作@MuktorFM。
deque 浅讲
deque（双端队列），支持两端进行操作，可近似地认为它就是 stack（栈）和 queue（队列）的结合体。
一些常用操作如下表（此处 即一个双端队列）：
| 代码 | 含义 |
|---|---|
q.push_front(x) |
在队首加入一个元素 |
q.push_back(x) |
在队尾加入一个元素 |
q.pop_front() |
在队首弹出一个元素 |
q.pop_back() |
在队尾弹出一个元素 |
q.clear() |
清空队列 |
q.emtpy() |
返回队列是否为空 |
q.size() |
返回队列大小 |
q.front() |
返回队首元素 |
q.size() |
返回队尾元素 |
有帮助，赞一个