单调队列

https://www.acwing.com/problem/content/156/

思考过程
1.暴力怎么做
2.队列当中有没有无用的值，怎么去掉
3.删掉多余的值，构造单调性
4.有了单调性，就有了极值，就优化了问题

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N], q[N];
int main()
{
    cin >> 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[]存在的是下标，如果要拿值，还要再套一层a[ ]
        q[++tt] = i;
        if (i >= k - 1)printf("%d ", a[q[hh]]);    //窗口里的数要有k个才可以输出，i从0开始计数
    }
    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]]);
    }
    puts("");
    return 0;
}

例题，NBUT - 1021