• 单调队列
• 例题
  • 洛谷P1886
  • 2023暑假训练-单调队列 单调栈

单调队列

单调的队列，即插入元素时保证队列是单调的。
去尾、删头、窗口
来维护一个单调队列

例题

洛谷：P2629

洛谷P1886

代码：

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;
}

2023暑假训练-单调队列 单调栈

传送门