滑动窗口核心思想
此题解基于y总提供的代码。
我们维护两个单调队列分别处理求滑动窗口中最小或最大元素的问题。对于求最小元素的问题,我们维护一个单增队列;对于求最大元素的问题,我们维护一个单减序列。
对于数组a和数组q我们要有清楚的认识:
数组a存储的是实际输入的数据,滑动窗口是在数组a上进行滑动;数组q是帮助我们模拟单调队列的逻辑结构。hh为队列头元素的下标,tt为队列尾元素的下标。当hh == tt时,我们认为队列为空。
数组q实际上存储的是对应元素的下标。q[hh]始终存储着每个滑动窗口中最小(或最大)元素的下标,同时它也表示着队列头元素;q[tt]表示着队列尾元素。
滑动窗口的长度始终为k,单调队列的长度是可变的,范围为[0,k];
当队列为空队列时,队列的长度为0;
滑动窗口内部k个元素的均满足单调队列的单调性时,队列的长度为k。
可以利用题目给出的数据结合代码进行手算检验。
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int main()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i ++ )scanf("%d", &a[i]);
int hh = 0, tt = -1;//hh为队头,tt为队尾
for(int i = 0; i < n; i ++ )//求最小
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;//当队头对应的a中元素下标落于滑动窗口之外时
while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;//若队尾元素大于等于新元素
q[ ++ tt] = i;//将新元素插入到队尾
if(i - k + 1 >= 0) printf("%d ", a[q[hh]]);//输出
}
cout << endl;
hh = 0, tt = - 1;//初始化队列
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)printf("%d ", a[q[hh]]);
}
return 0;
}