单调队列问题——滑动窗口
题意分析
本题是一个模板题,就是利用队列维护滑动窗口里面的(最小/最大)值,题意分析完了,那么什么是单调列队列呢?
单调队列是什么
顾名思义,单调队列就是队列里面的值具有单调性(递增/递减)。
单调队列的基本思想是,维护一个双向队列(deque),遍历序列,仅当一个元素可能成为某个区间最值时才保留它。
实现过程
- 窗口新加入值的时候,先判断队头元素是否在窗口范围内,如果队头元素超出了窗口范围的话,弹出队头元素。
- 每次新加元素的时候,和队尾元素进行比较,假如说我们维护的是单调递增序列的话,如果队尾元素比新增元素大的时候,那么此时队列就不具有单调性,那么此时就弹出队尾元素。
思考
为什么我们要维护队列的单调性呢?
前提队列内的值一定是在滑动窗口范围内的,这点是毋庸置疑的,这是上述实现过程中所实现的。
原因:假如说我们现在有一个数组[2,4,3,5,2,6]
,滑动窗口的范围是3,且滑动窗口的所处的位置是[4,3,5]
,那么此时单调队列里的元素是[3,5]
,队列元素具有单调性,此时新元素2
要加入队列,所以队列更新完之后应该为[2]
,这么做的原因是,新加元素2
的值,在窗口内且比3
和5
小,那么3
和5
将不会再用到了。换句话说,只要2在,那么3
和5
永无出头之日。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n,k;
int a[N];
int q[N];
int hh = 0, tt = -1;
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
//求最小值
for(int i = 0; i < n; i++){
if(hh <= tt && i - k + 1 > q[hh]) hh++;//判断队头是否超出滑动窗口的范围
while(hh <= tt && a[q[tt]] >= a[i]) tt--;//维护队列的单调性
q[++tt] = i;//在保证队列单调性的前提下,加入元素至队尾
if(i - k + 1 >= 0) cout << a[q[hh]] << " ";//如果滑动窗口存在的话,输出队头元素
}
//求最大值
hh = 0, tt = -1;
cout<<endl;
for(int i = 0; i < n; i++){
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i - k + 1 >= 0) cout << a[q[hh]] << " ";
}
return 0;
}