单调队列的思考方式：

  1. 思考使用普通队列该怎么做？
  2. 将队列中没有用的元素删除掉 --> 具有单调性
  3. 可以用O(1)的时间从队头或者队尾取出最值

单调队列的使用条件：

  1. 求窗口里面的最大值或者最小值，常规做法是遍历这个窗口O(k)，使用单调队列可以优化为O(1)
  2. 求离它最近的比它小（大）的数

本题（滑动窗口）的思考方式：

首先，我们使用队列来模拟这个滑动的窗口，因为队列的先入先出特性正好和滑动的窗口一致，然后就考虑如何去优化——**删除一些冗余（肯定不会被用到）**的元素，从而使得队头元素恰好是需要的元素。

这里有两个问题需要求解：

  • 如何维护这个队列（使之与滑动的窗口对应）？
  • 如何删除冗余？

代码实现实在是太巧妙了hh

还有一个注意点：队列q中存放的是元素的下标，不是元素数值！

if(hh <= tt && q[hh] < i - k + 1) hh++;//从队列中删除超出滑动窗口的元素
while(hh <= tt && a[q[tt]] >= a[i]) tt--;//删除冗余
q[++tt] = i;//向队列中增加元素=向滑动窗口中增加元素

代码实现

//单调队列
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int a[N], q[N];//a是原数组,q是手动模拟队列
int n, k;

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

    int hh = 0, tt = -1;//初始化队列
    for(int i = 0; i < n; i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;//左边元素出滑动窗口，对应队列出队
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;//删除冗余
        q[++tt] = i;//右边元素进滑动窗口，对应队列入队，注意入队的是元素的下标

        if(i >= k - 1) cout << a[q[hh]] << " ";//打印队列最左边的元素，即最小值
    }
    puts("");

    hh = 0, tt = -1;
    for(int i = 0; i < n; i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;

        if(i >= k - 1) cout << a[q[hh]] << " ";
    }
    puts("");
    return 0;
}