这题怎么写啊没有一点思路QWQ求助

LHX05 @ 2023-08-12 16:14:56

by Alexandra @ 2023-08-12 16:16:12

看题解

by Li_wc0802 @ 2023-08-16 09:18:24

你可以这么写

#include<iostream>
using namespace std;
int p[1000001];
int q[1000001],head=1,tail,n,a[1000001],k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    q[0]=-999999999;
    for(int i=1;i<=n;i++)
    {
        while(a[i]<q[tail]&&head<=tail)tail--;
        q[++tail]=a[i];
        p[tail]=i;
        while(i-k+1>p[head])head++;
        if(i>=k)cout<<q[head]<<' ';
    }
    cout<<endl;
    head=1,tail=0;
    q[0]=99999999;
    for(int i=1;i<=n;i++)
    {
        while(a[i]>q[tail]&&head<=tail)tail--;
        q[++tail]=a[i];
        p[tail]=i;
        while(i-k+1>p[head])head++;
        if(i>=k)cout<<q[head]<<' ';
    }
    return 0;
}

希望有帮助