单调队列

描述见题面
思路：单调队列，遍历所有元素，并维护一个队列（以最大值为例），此队列中，队头表示的是当前窗口内的最大值，其他的是可能成为最大值的候选，并且越在队列的后面生命周期越长，假设当前遍历到了下标为 i 的元素，那么首先要检验一下队列中那个“最老”的元素，即队头还在不在窗口范围内，若不在就弹出，因为每次只会遍历下一个元素，所以此操作每次循环最多执行一次，接着就来看这个下标为 i 的元素，只要当前这个a[i] > 队尾元素，就让他替换当前队尾，直到队尾比他大。然后每一次输出队头即可。
代码：

// 单调队列求解，数组模拟队列
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N];
int q[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

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

        q[ ++ tt] = i;
        if (i + 1 >= m) printf("%d ", a[q[hh]]); 
    }

    puts("");

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

        q[ ++ tt] = i;
        if (i + 1 >= m) printf("%d ", a[q[hh]]); 
    }

    return 0;
}