AcWing 154. 滑动窗口

# 滑动窗口 - 单调队列

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, k;

int a[N], q[N];

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int 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) printf("%d ", a[q[hh]]);
    }
    puts("");
    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) printf("%d ", a[q[hh]]);
    }
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, k;

int a[N], q[N];

int main(){
    scanf("%d%d", &n, &k);
    
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    int 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) printf("%d ", a[q[hh]]);
    }
    
    puts("");

    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) printf("%d ", a[q[hh]]);
    }
    return 0;
}

# 具有单调性的模拟队列

1. 用普通队列该怎么做
2. 将队列中的没有用的元素删掉 -> 具有了单调性
i - k + 1 是以 i 为右端点、长度为 k 的区间的左端点，如果 q [hh] 的值比左端点小，那就说明队头节点已经不在区间中了，需要弹出。
3. 可以用 O (1) 时间从队头 / 队尾取出最值

# 为什么 i-k+1 > q [hh] 不能写成 i-k+1 > hh，还是不清楚为啥拿存储下标可以判断对头是否出队

因为下标可以唯一对应到数组值同时维护窗口长度不超过 k，而数组可能有重复值，没法和下标一一对应也就不能保证窗口的大小。