基础数据结构

Qiansui / 2023-06-13 / 原文

单调队列

去尾、删头、窗口
来维护一个单调队列
例题：
1.https://www.luogu.com.cn/problem/P1886
代码：

//>>>Qiansui
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
const int maxm=1e6+5,inf=0x3f3f3f3f,mod=998244353;
ll n,k,a[maxm];
deque<ll> q;//单调队列

void solve(){
	cin>>n>>k;
	ll t;
	for(int i=0;i<n;++i) cin>>a[i];
	for(int i=0;i<n;++i){
		while(!q.empty()&&a[q.back()]>a[i])//去尾
			q.pop_back();
		q.push_back(i);
		if(i>=k-1){
			while(!q.empty()&&q.front()<=i-k)
				q.pop_front();//删头
			cout<<a[q.front()]<<" \n"[i==n-1];
		}
	}
	q.clear();
	for(int i=0;i<n;++i){
		while(!q.empty()&&a[q.back()]<a[i]){
			q.pop_back();
		}
		q.push_back(i);
		if(i>=k-1){
			while(!q.empty()&&q.front()<=i-k)
				q.pop_front();
			cout<<a[q.front()]<<" \n"[i==n-1];
		}
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}