C++ 代码

#include <iostream>
using namespace std;
const int N=1e6+10;
int q[N];   //单调队列，但储存的并不是数，而且数组下标，即位置，再通过a[q[i]]得到值
int a[N];   //储存读入的数
int main()
{
    ios::sync_with_stdio(false);    //加速读入
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin >> n >> k;
    for(int i=0; i<n; ++i)  //滑动窗口，单调队列
        cin >> a[i];
    int head=0,tail=-1;     //我也不晓得为什么开始要这样2333,总之就是head要设为窗口最开始即为0吧，且为了保持统一，不特判，因为后面有元素入队操作q[++tail] = i，所以tail开始置为-1，++之后就到窗口最开始即0了吧
    for(int i=0; i<n; ++i){     //全部读入后一个个对数组元素进行处理
        if(head <= tail && i-q[head]+1 > k)     //当队列不为空即head<=tail 且当前队列中的长度(i为当前元素，即滑动窗口的最右端，q[head]为滑动窗口的最左端，窗口长度为i-q[head]+1)大于题目中给出的窗口长度k时
            ++head;     //队头元素(窗口最左端元素)出队
        while(head <= tail && a[q[tail]] >= a[i])   //当队列不为空，且当前处理元素a[i]更小时，因为a[i]左边比a[i]更大的值a[max](即a[tail]) 与a[i]在同一个窗口时，(且a[i]在a[tail]右侧,所以a[i]存在时间比a[tail]的更长) a[tail]不可能会被选中,所以去除a[tail],即使得a[tail]出队
            --tail;     //队尾元素(窗口最右端元素)出队，特殊情况，非正常队列出队
        q[++tail] = i;  //将当前处理元素i(a[i])入队
        if(i+1 >= k)    //因为队列中的元素是一个个增加，逐个处理的，而很明显只有当滑动窗口内(不算上已清除的)元素个数满足k时，才会输出最小值，比如总共8个元素，k=3,所以会输出8-3+1=6个元素，就是因为刚开始时处理窗口元素个数过少，不会输出元素
            cout << a[q[head]] << " ";  //由于队列(即滑动窗口)中元素为单调递增的(单调队列+处理的性质)，所以head,即窗口最左端元素为最小值
    }
    cout << endl;
    head = 0,tail = -1;     //输出最大值，与上述类似
    for(int i = 0; i < n; ++i){
        if(head <= tail && i-q[head]+1 > k)
            ++head;
        while(head <= tail && a[q[tail]] <= a[i])   //这里改为若队列元素小于等于当前处理元素就出队
            --tail;
        q[++tail] = i;
        if(i+1 >= k)
            cout << a[q[head]] << endl;
    }
    cout << endl;
    return 0;
}