Ikari_Shinji @ 2019-01-19 21:02:10

#include<cstdio>
#include<cstring>

const int N=1e6+5;
int a[N],f[N],n,k,h=0,t=0;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[1]=2147483647;
    for(int i=1;i<=n;i++){        
        if(f[h]<=i-k)h++;
        while(t>=h&&a[f[t]]>=a[i])
            t--;
        f[++t]=i;
        if(i>=k)
            printf("%d ",a[f[h]]);
    }
    printf("\n");
    memset(f,0,sizeof(f));
    f[1]=-2147483648;
    for(int i=1;i<=n;i++){        
        if(f[h]<=i-k)h++;
        while(t>=h&&a[f[t]]<=a[i])
            t--;
        f[++t]=i;
        if(i>=k)
            printf("%d ",a[f[h]]);
    }
    printf("\n");
    return 0;
}

by resftlmuttmotw @ 2019-01-19 21:08:16

@基神_Freedom

#include <cstdio>
using namespace std;
const int MAXN = 1000001;
int num[MAXN],q[MAXN],it[MAXN],q1[MAXN],it1[MAXN];
int ALL,Begin,End,Begin1,End1,pr[MAXN];
int main()
{
    int n,k,i;
    scanf("%d%d",&n,&k);
    for(i = 1;i <= n;i++)
        scanf("%d",&num[i]);

    for(i = 1;i <= n;i++)
    {
        if(Begin == 0)
        {
            ++Begin,++End;
            q[Begin] = num[i];
            it[Begin] = i;
            ++Begin1,++End1;
            q1[Begin1] = num[i];
            it1[Begin1] = i;
        } else {
            while(q[End] >= num[i]&&End >= Begin)
                --End;
            End++;
            q[End] = num[i];
            it[End] = i;
            while(q1[End1] <= num[i]&&End1 >= Begin1)
                --End1;
            End1++;
            q1[End1] = num[i];
            it1[End1] = i;
        }
        if(i >= k)
        {
            while(it[Begin] < i - k + 1)
                Begin++;
            while(it1[Begin1] < i - k + 1)
                Begin1++;
            ALL++;
            pr[ALL] = q1[Begin1];
            printf("%d ",q[Begin]);
        }
    }
    putchar('\n');
    for(i = 1;i <= ALL;i++)
        printf("%d ",pr[i]);
}

好羡慕你们这些周末还能静下心来刷题的人

by Ikari_Shinji @ 2019-01-19 21:11:04

@resftlmuttmotw DALAO可以解释一下我的代码哪里有错吗？

by resftlmuttmotw @ 2019-01-19 21:14:37

@基神_Freedom

不不不大佬就自己DEBUG吧

大佬一定可以的

实在不行

@ 这位

Panda_hu

by GKxx @ 2019-01-19 21:23:29

@基神_Freedom

你第二遍求最大值的时候没复原队列的指针h和t吧

这样的话你队列数组要开两倍长

by Ikari_Shinji @ 2019-01-19 21:27:46

@GKxx 是的，谢谢！