单调队列的功能
单调队列，这个神奇的 \(O(n)\) 算法，经常有人把他和优先队列混为一谈，但实际上两者大相径庭。
总的来说，单调队列有两个功能：
-
可以从队头/队尾出队，而且出入顺序正常。
-
可以按照增/减/自定义比较方式求出队中最值。
单调队列有一个很著名的 \(Sliding\) \(Window\) (滑动窗口) 问题。该问题原型是：给定一个数组和一个窗口长度，求该窗口划过数组时，窗口框选的数字最值是多少。详见P1886 滑动窗口。
单调队列的实现
单调队列需要手写模拟，实现方式也不是很难，请看代码：
#include<bits/stdc++.h>
using namespace std;
struct monotonic_queues{
int n,k,a[1000001];
int q[1000001],l,r,p[1000001];
void read(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
}
void monotonic_max(){
l=1;
r=0;
for(int i=1;i<=n;i++){
while(l<=r&&q[r]<=a[i]){
r--;
}
q[++r]=a[i];
p[r]=i;
while(p[l]<=i-k){
l++;
}
if(i>=k)cout<<q[l]<<' ';
}
cout<<'\n';
}
void monotonic_min(){
l=1;
r=0;
for(int i=1;i<=n;i++){
while(l<=r&&q[r]>=a[i]){
r--;
}
q[++r]=a[i];
p[r]=i;
while(p[l]<=i-k){
l++;
}
if(i>=k)cout<<q[l]<<' ';
}
cout<<'\n';
}
}worker;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
worker.read();
worker.monotonic_min();
worker.monotonic_max();
return 0;
}