单调递增队列:
后面的元素比前面的元素小,则前面的元素没有意义删掉;
线性扫描找队列最值,需要o(K);单调队列,队头即最值,复杂度o(1).
单调队列应用: 窗口极值,临近极值
滑动窗口思路:
维护一个单调队列,队列的size可变,但队列的tt-head+1为窗口大小;
滑动窗口,每次滑进一个元素;
注释:
1.存储从i-k+1到i下标,共k个。
2.q[hh]队列存储的是a数组下标,所以访问的时候,要加a[q[hh]]访问
3.滑出元素时,不用加hh <= tt 约束,因为hh不会无限++;但维护队列单调性时,tt可能会持续--
4.初始状态,hh必需比tt多一; 例: hh = 0, tt = -1; 或 hh = 1, tt = 0都可;
若相等 例:hh==tt==0, 因为tt移动是++tt,则hh 将存储值;所以用到q[hh]的地方,
将会出现逻辑错误,所以,如果tt指向尾元素(用++tt进行入队),则hh必需比tt多一;
若tt指向尾元素后一元素(用tt++入队),则初始可hh==tt; --推荐
5.if (i - k + 1 > q[hh]) hh++;当>q[hh]时才滑动,并不是每次循环滑出一个;
因为是单调队列,有的下标并没有存储,比如样例:
1 3 -1 -3
0 1 2 3
当队列存储下标2后,下标0,1就pop了,q[hh]为2,此时i遍历到下标3,则i-k+1 为1<2,不pop;
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N]; //原数组、队列
int hh, tt;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < n; i ++ ) //枚举原数组作为滑动窗口的右端点。
{
//当前窗口k个元素:i-k+1 到 i
if (i - k + 1 > q[hh]) hh ++ ;
//当前队尾元素>=入队元素则出队,维护队列的单调性
while (hh < tt && a[q[tt-1]] >= a[i]) tt -- ;
q[tt ++] = i;
//i从k-1开始才构成窗口
if (i >= k - 1) printf("%d ", a[q[hh]]); //当前窗口最小值,队头元素
}
puts("");
hh = tt = 0;
for (int i = 0; i < n; i ++ )
{
if (i - k + 1 > q[hh]) hh ++ ;
while (hh < tt && a[q[tt-1]] <= a[i]) tt -- ;
q[tt ++] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}