单调队列（双端队列）

先考虑在窗口内取最小值的情况

在窗口移动的时候，只在乎上一个窗口的最小值x是否会被移除，若移除的话，要知道当前窗口的最小值y，只需要有维持一个序列，可以让我们知道，移除掉x后y的值

因为只在乎去除最小值后的次小值，可以使用一个单调递增的队列

在窗口增长阶段

当窗口大小达到k后，取出队首就是该窗口的最小值

窗口移动阶段

1.如果最小值不在窗口内，将最小值移除，即弹出队首，然后判断一下新入队的元素与队列其他元素的关系，继续维持序列递增
新入队的元素如果放在队列内部，会导致一部分元素弹出，由于新元素的位置靠后，所以对其他窗口并不会造成影响
2.如果最小值在窗口内，此窗口最小值与上一个窗口相同

由于需要对队列两端进行操作，需要使用双端队列

同理，再取最大值的时候，将队列的单调性取反就可以了

#include <iostream>
#include <deque>

using namespace std;

const int N = 1000005;
typedef pair<int, int> PII;
int a[N], k, n;
deque<PII>q;

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

    for(int i = 0; i < n; i++)
    {
        while(q.size() && q.back().first > a[i]) q.pop_back();
        q.push_back({a[i], i});   //判断一个元素是否超出窗口范围，可以在将值入队的同时，保存索引
        if(i >= k - 1) cout << q.front().first << " ";
        if(q.front().second == i - k + 1) q.pop_front();
    }
    cout << endl;

    q.clear();

    for(int i = 0; i < n; i++)
    {
        while(q.size() && q.back().first < a[i]) q.pop_back();
        q.push_back({a[i], i});
        if(i >= k - 1) cout << q.front().first << " ";
        if(q.front().second == i - k + 1) q.pop_front();
    }
    cout << endl;

    return 0;
}