标签：练手 队列 P1886 板子 int https include 最值
板子题，传送门在上方
// 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;
}
标签：练手,
队列,
P1886,
板子,
int,
https,
include,
最值
From： https://blog.csdn.net/why_not_fly/article/details/136665319
https://www.luogu.com.cn/problem/P1886