手写单调队列

单调队列的功能

单调队列，这个神奇的 \(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;
}