C++

$\color{#cc33ff}{— > 算法基础课题解}$

#include<iostream>
#include<stdio.h>
using namespace std;

const int N = 1e6 + 10;
int n, k;
int a[N], q[N];//a存原来的值，q是单调队列

int main(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]); //输入数组


    //求滑动窗口的最小值
    int hh = 0, tt = -1;//定义队列的队头和队尾，hh:队头，tt:队尾 (开始时队列是空的)
    for (int i = 0; i < n; i ++) {
        //判断队头是否已经划出了窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++; //先判断一下队列是否是空的以及如果i - k + 1 > q[hh],说明已经出了滑动窗口了, hh ++
        //同时之所以用if而不是while,是因为每次窗口只往后移动一位，所以队列里最多只会有一位不在窗口内

        while(hh <= tt && a[q[tt]] >= a[i]) tt --;//如果此时窗口的最后一个数比即将要加入窗口的这个数a[i]大，那么窗口的这最后一个数就要删除
        // 队列里面存储的是下标，要取值的话还要套一层a数组

        q[ ++ tt] = i; // 把当前这个数的下标i插到队列里面去
        if (i >= k - 1) printf("%d ", a[q[hh]]); // 当我们的数大于k个的时候，才需要输出
    }
    cout << endl; // 输出回车


    //求滑动窗口的最大值
    hh = 0, tt = -1;//定义队列的队头和队尾，hh:队头，tt:队尾 (开始时队列是空的)
    for (int i = 0; i < n; i ++) {
        //判断队头是否已经划出了窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++; //先判断一下队列是否是空的以及如果i - k + 1 > q[hh],说明已经出了滑动窗口了, hh ++
        //同时之所以用if而不是while,是因为每次窗口只往后移动一位，所以队列里最多只会有一位不在窗口内

        while(hh <= tt && a[q[tt]] <= a[i]) tt --;//如果此时窗口的最后一个数比即将要加入窗口的这个数a[i]小，那么窗口的这最后一个数就要删除
        // 队列里面存储的是下标，要取值的话还要套一层a数组

        q[ ++ tt] = i; // 把当前这个数的下标i插到队列里面去
        if (i >= k - 1) printf("%d ", a[q[hh]]); // 当我们的数大于k个的时候，才需要输出
    }
    cout << endl;

    return 0;
}