普通队列超时版

/*
滑动窗口的大小为k, 每一次维护一个区间的最小和最大值, 每次新加入的元素若是比之前的大，那么就更新一下，如果没有那么就不更新
数据结构的选取： 队列
特殊的, 当滑动窗口的大小为 n或1 的时候那么最小值和最大值就是整个数组的最小最大值，前者输出一个，后者输出n个
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,k;
int a[N];
vector<long long> qmi;
vector<long long> qmx;
queue<long long> q;

// 默写快读模板
int rd(){
    // 初始化k
    int k = 0;
    // 循环吞掉非数字符号
    char c = getchar();
    while(!isdigit(c)){
        c = getchar();
    }
    // 循环转换数字符号为数字
    while(isdigit(c)){
        k = (k << 1) + (k << 3) + (c ^ '0'), c = getchar();
    }
    // 返回数字
    return k;
}


int main(){
    n = rd();
    k = rd();
    for(int i = 0; i < n ; i ++){
        cin >> a[i];
    }
    // 判断特殊情况
    // 找到数组的最小值和最大值
    long long mi = *min_element(a,a+n);
    long long mx = *max_element(a,a+n);
    if(k == 1){
        for(int i = 0 ; i < n ; i ++ ){
            cout << a[i] << " ";
        }
        cout << endl;
        for(int i = 0 ; i < n ; i ++ ){
            cout << a[i] << " ";
        }
        return 0;
    }
    if(k == n){
        cout << mi << endl << mx;
        return 0;
    }
    // 滑动窗口
    // 清空mi和mx
    mi = *min_element(a,a+k);
    mx = *max_element(a,a+k);
    // 存储最大最小元素
    qmi.push_back(mi);
    qmx.push_back(mx);
    // 队列中需要时刻保持拥有k个元素
    for(int i = 0 ; i < k ; i ++){
        q.push(a[i]);
    }
    for(int i = 1; i <= n - k; i ++){ // 枚举左端点(从1开始)
        // 入队 
        q.push(a[i+k-1]);
        // 队列的尾元素（新元素）假如大于当前的最小值那么就更新一下
        if(q.back() <= mi) mi = q.back();
        if(q.back() >= mx) mx = q.back();
        // 出队
        // 如果即将出队的元素是最大值或者最小值，那么重新选举最大值或最小值
        if(q.front() == mi){
            mi = *min_element(a+i+1,a+i+k+1);
        }
        if(q.front() == mx){
            mx = *max_element(a+i+1,a+i+k+1);
        }
        // 元素出队
        q.pop();
        // 维护最小最大元素
        qmi.push_back(mi);
        qmx.push_back(mx);
    }

    for(int i=0;i<qmi.size();i++){
        cout << qmi[i] << " ";
    }
    cout << endl;

    for(int i = 0; i <qmx.size(); i++){
        cout << qmx[i] << " ";
    }
    return 0;
}

单调队列版

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
ll n,k;
ll a[N],q[N];// 定义原数组和单调队列


int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    // 单调队列[最小值]
    // 初始化队列
    int hh = 0,tt = -1;
    // 循环遍历每一个元素
    for(int i=0;i<n;i++){
        // 是否头出？前人退休 (i - k + 1)代表当前的窗口在数组中的首地址
        // if(hh <= tt && hh < i - k + 1) hh ++;
        // hh 和 (i - k + 1)没有直接逻辑关系，因为 hh 是队列指针，而 i - k + 1 是数组下标。
        if(hh <= tt && q[hh] < i - k + 1) hh ++;
        // 循环新来的更强(因为是求最小值，所以更小)则退位 // 比最大的还要小故为最小
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        // 取而代之
        q[++ tt] = i; // 存入下标
        // 当前元素至少大于等于k（第一个窗口大小）则输出头元素（头元素是最小的)
        // 我的理解是日拱一卒，每次新增元素导致都是一次移动，每次移动如果是新人更强则清除前人，如果是前人更强则不管新人如何累积，直到退休就在头队出队让仅此的后人即可
        if(i >= k - 1) cout << a[q[hh]] << " ";
    }

    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) cout << a[q[hh]] << " ";
    }
    return 0;
}