$$ 单调队列 $$

1.定义： 一个满足内部单调递增或者递减的数据结构

2.实质（实现方式）： 双端队列

3.应用： 利用其单调性，常用来维护区间最值问题， 或者降低DP维数，以达到降低空间及时间的目的

4.性质：

• 队列中的元素对应原来列表的位置（即下标）必须是单调递增（递减）的
• 队列中的元素必须是单调递增（递减）的

求区间最值例题：滑动窗口

分析：对于求最大值(求最小值一样):

• 维护队首：队列首下标小于当前元素下标的 k 个之前（就是队列的长度超出了要求），弹出队首
• 维护队尾：比较当前元素与队尾元素的大小，若当前元素更大，一直弹出队尾，直到满足队尾元素更大。

原因：对于$a_x$ 和 $a_y$,$x < y$且$a_x < a_y $ 那么队列在加入元素 $a_y$之后$a_x$就再也不可能是最大值了，直接踢掉.

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 5;

int n, k;
int a[N];
int q[N], v[N];
// q --> 添加元素，维护队尾 v --> 添加下标，维护队首
// 不过也有 只用一个数组 q 充当小标， 此时， a[q[tt]] 为队尾元素 a[q[hh]] 队首元素

void maxx(){
    int tt = 0, hh = 1;                         // 队列初始化
    for(int i = 1; i <= n; i++){                // 遍历所有元素，是否加入队列
        while(tt >= hh && q[tt] < a[i]) tt -- ; // 当队列不为空 并且 队尾元素小于当前值， 队尾出队
        q[++tt] = a[i];                         // 加入当前元素
        v[tt] = i;                              // 记录下标
        while(v[hh] <= i - k) ++ hh;            // 当对头元素小于 i - k,即队列长度超出要求，队首出队
        if(i >= k) printf("%d ", q[hh]);        // 当队列全部进去才输出（滑动窗口从全部进来了）
    }
}

void minn(){
    int tt = 0, hh = 1;                         // 初始化
    for(int i = 1; i <= n; i++){
        while(hh <= tt && q[tt] > a[i]) tt--;   // 是否满足条件
        q[++tt] = a[i];                         // 添加当前元素
        v[tt] = i;                              // 队首添加下标
        while(v[hh] <= i - k) ++ hh ;           // 判断是否超出限制大小
        if(i >= k) printf("%d ", q[hh]);
    }puts("");
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    minn(); maxx();

    return 0;
}