AcWing 154. 滑动窗口(单调队列)
思路：先求滑动窗口的最小值，对暴力做法进行优化，用一个队列维护滑动窗口，如果某个窗口内的某个位置 i 的值比前面的元素小，那么在这个窗口和后面的窗口中 i 前面的元素一定是不会被输出的，就可以删掉，这样得到的队列一定是单调递增的，队头为最小值。
如果队头元素的位置超出窗口的范围要对队列进行删减。
因为在一个窗口中最小元素的位置是不确定的，所以队列要存储元素的位置
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,k;
int arr[N],q[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
int hh=1,tt=0;
for(int i=1;i<=n;i++){
if(hh<=tt&&q[hh]<=i-k){
hh++;
}
while(hh<=tt&&arr[q[tt]]>=arr[i]){
tt--;
}
q[++tt]=i;
if(i>=k){
cout<<arr[q[hh]]<<" ";
}
}
cout<<endl;
hh=1;tt=0;
for(int i=1;i<=n;i++){
if(hh<=tt&&q[hh]<=i-k){
hh++;
}
while(hh<=tt&&arr[q[tt]]<=arr[i]){
tt--;
}
q[++tt]=i;
if(i>=k){
cout<<arr[q[hh]]<<" ";
}
}
return 0;
}
