单调队列
考虑在一个序列中维护一个类似于窗口的东西。
以下不妨设求得是窗口最大值。
首先根据贪心，如果当前数整个窗口中最大的，并且是最靠前的，那么这个数前面的所有数都不会对答案产生一点贡献。于是考虑维护一个单调递增的序列，需要从中找出答案。设置一个首指针，未指针代表这个窗口的开始和结束。
然后，考虑一个和莫队类似的操作：
Remove操作：将比当前值小的数扔出维护序列即可。
Add操作：直接将当前数加入到队伍的最后段（这里可以仔细想一想，为什么）。
然后按照这样的操作模拟即可。
时间复杂度分析
这是很简单的，因为每一个元素最多只被出队和入队各 \(1\) 次，所以时间复杂度是 \(O(n)\)。
模板
模板题目：P1886 滑动窗口
AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1000;
int n,k;
int number[N];
int num[N];
int main(){
ios::sync_with_stdio(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>number[i];
int fst=0,ed=-1;
for(int i=1;i<k;i++){
while(fst<=ed&&number[num[ed]]>=number[i])ed--;
num[++ed]=i;
}
for(int i=k;i<=n;i++){
while(fst<=ed&&number[num[ed]]>=number[i])ed--;
num[++ed]=i;
while(num[fst]<=i-k)fst++;
cout<<number[num[fst]]<<' ';
}
for(int i=0;i<=ed;i++)num[i]=0;
fst=0,ed=-1;
cout<<'\n';
for(int i=1;i<k;i++){
while(fst<=ed&&number[num[ed]]<=number[i])ed--;
num[++ed]=i;
}
for(int i=k;i<=n;i++){
while(fst<=ed&&number[num[ed]]<=number[i])ed--;
num[++ed]=i;
while(num[fst]<=i-k)fst++;
cout<<number[num[fst]]<<' ';
}
return 0;
}
优点分析
单调队列可以在 \(O(n)\) 的时间复杂度之内求出一个给定区间长度的整个序列中的区间最大值，在这一点上，它比 线段树 和 ST表 优化了一个 \(O(\log n)\) 的时间。
例题
P2698
题目形式化：