单调队列

这道题目是典型的单调队列的题目
要注意如下几点，队头始终保存着滑动窗口中最大或者最小的元素，然后队列里按从大到小或者从小到大存放着其他有元素

比如窗口 5 3 4 6 ，队列里的存放顺序为 3 4 6,但是没有5 因为5已经不是有效元素了，因为3在5后面，而窗口是在像右滑动，5是比3先出窗口的。
3出去后，4有可能成为下一个最小元素，但5已经没可能了。

核心代码就是入队和出队操作：
出队：
1：队头元素已经离开窗口
2：从队尾开始，将所有比待入队元素大的元素出队

入队：
完成出队操作后，将待入队元素入队

需要注意的点就是，为了方便判断什么时候队头元素出队，所以队列中存储的是数组中对应元素的下标
如此便可使用 i - k + 1 > stk[head]就可以判断当前队头元素是否已经出队了

C++ 代码

#include <iostream>
using namespace std;
const int N = 1000010;
int q[N],stk[N];
int head , tail;
int main(){
    int n , k;
    cin >> n >> k;
    for(int i = 0;i < n; ++i){
        cin >> q[i];
    }
    head = 0;
    tail = -1;
    for(int i = 0;i < n;++i){
        if(head <= tail && i - k + 1 > stk[head]) ++head;
        while(head <= tail && q[stk[tail]] >= q[i]) --tail;
        stk[++tail] = i;
        if(i - k + 1 >= 0) cout << q[stk[head]] << " ";
    }
    cout << endl;
    head = 0;
    tail = -1;
    for(int i = 0;i < n;++i){
        if(head <= tail && i - k + 1 > stk[head]) ++head;
        while(head <= tail && q[stk[tail]] <= q[i]) --tail;
        stk[++tail] = i;
        if(i - k + 1 >= 0) cout << q[stk[head]] << " ";
    }
    return 0;
}