单调队列 维护区间最值（板子+两道练手）

1.P1886 滑动窗口 /【模板】单调队列https://www.luogu.com.cn/problem/P1886

板子题，传送门在上方

// Problem: 
//     P1886 滑动窗口 /【模板】单调队列
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1886
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<deque>
#include<vector>
using namespace std;

int main(){
	int n,m;cin>>n>>m;//板子
	deque<int> d;
	vector<int> a(n+1);
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i){
		while(d.size()&&a[d.back()]>a[i]) d.pop_back();///丢出大于它的，就可以维护一定区间的最小了
		d.push_back(i);
		if(i>=m){
		    while(d.size()&&d.front()<=i-m) d.pop_front();//这里注意是q.front 因为存的下标
		    cout<<a[d.front()]<<' ';
        }
	}
	cout<<endl;
	while(d.size()) d.pop_front();
	for(int i=1;i<=n;++i){
		while(d.size()&&a[d.back()]<a[i]) d.pop_back();
		d.push_back(i);
		if(i>=m){
		    while(d.size()&&d.front()<=i-m) d.pop_front();
		    cout<<a[d.front()]<<' ';
        }
	}
	cout<<endl;
	
	
	
	
	
	
	return 0;
}

P2032 扫描

P1440 求m区间内的最小值