注释版题解C++

#include<iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N]; //a[N]存储输入数据，q[N]存储a中元素的下标
int n, k;

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]); //输入数据
    int hh = 0, tt = -1; //定义头尾指针，hh为头，tt为尾，hh > tt则队列为空
    for(int i = 0; i < n; i++){
        if(hh <= tt && q[hh] < i - k + 1) //如果队列非空 且当前维持的窗口长度超过了题目定义的窗口k
            hh++;               //即就是i减去队列头（存储的是下标，表示的是当前窗口的左端点）中的值所得长度超过k
                                //那么维持的窗口左端点就要向右移动，由于每次只最多进行一个元素的添加，这里用if判断而不用while
        while(hh <= tt && a[q[tt]] >= a[i])
            tt--;
        q[++tt] = i;  //将当前元素的下标加入队列尾
        if(i >= k - 1)  //此处主要作用是最开始时的输出判断，最开始需要i值达到窗口长度才能进行输出
            printf("%d ", a[q[hh]]); //比如窗口为3，i循环到1，维持的窗口最大为2，还没达到输出的要求
    }
    cout << endl;
    //以下输出最大值，原理同最小值求解
    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)
            printf("%d ", a[q[hh]]);
    }
    cout << endl;
    return 0;
}