C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

int n,k;
int a[N],q[N];//a[n]存原来的数 q[n]是队列

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

    int hh=0,tt=-1;//队头 队尾
    for(int i=0;i<n;i++)
    {
        //判断队头是否已经划出窗口
        //注意：队列存的下标 窗口每次只会移动一位
        if(hh<=tt && i-k+1>q[hh])hh++;//hh<=tt队列不空 //队头元素出队

        while(hh<=tt && a[q[tt]]>=a[i])tt--;//

        q[++tt]=i;//队列里放一个元素（下标）
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    puts("");

    hh=0,tt=-1;//队头 队尾
    for(int i=0;i<n;i++)
    {
        //判断队头是否已经划出窗口
        //注意：队列存的下标 窗口每次只会移动一位
        if(hh<=tt && i-k+1>q[hh])hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i-k+1>=0)printf("%d ",a[q[hh]]);
    }
    puts("");
}