单调队列 WA 4、5、7 70 分求助

IYSY2009I @ 2023-05-01 13:31:25

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int a[1000005];
deque<int> q;
deque<int> id;
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=k; i++) {
        while(!q.empty()&&q.front()>=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        q.push_back(a[i]);
        id.push_back(i);
    }
    printf("%d ",q.front());
    for(int i=k+1; i<=n; i++) {
        while(!id.empty()&&id.front()<=i-k) {
            q.pop_front();
            id.pop_front();
        }
        while(!q.empty()&&q.back()>=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        id.push_back(i);
        q.push_back(a[i]);
        printf("%d ",q.front());
    }
    q.clear();
    id.clear();
    printf("\n");
    for(int i=1; i<=k; i++) {
        while(!q.empty()&&q.front()<=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        q.push_back(a[i]);
        id.push_back(i);
    }
    printf("%d ",q.front());
    for(int i=k+1; i<=n; i++) {
        while(!id.empty()&&id.front()<=i-k) {
            q.pop_front();
            id.pop_front();
        }
        while(!q.empty()&&q.back()<=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        id.push_back(i);
        q.push_back(a[i]);
        printf("%d ",q.front());
    }
    return 0;
}

by DreamLand_zcb @ 2023-05-01 14:25:41

@IYSY2009I

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int a[1000005];
deque<int> q;
deque<int> id;
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<k; i++) {
        while(!q.empty()&&q.back()>=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        q.push_back(a[i]);
        id.push_back(i);
    }
    for(int i=k; i<=n; i++) {
        while(!q.empty()&&q.back()>=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        id.push_back(i);
        q.push_back(a[i]);
        while(!id.empty()&&id.front()<=i-k) {
            q.pop_front();
            id.pop_front();
        }
        printf("%d ",q.front());
    }
    q.clear();
    id.clear();
    printf("\n");
    for(int i=1; i<k; i++) {
        while(!q.empty()&&q.back()<=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        q.push_back(a[i]);
        id.push_back(i);
    }
    for(int i=k; i<=n; i++) {
        while(!q.empty()&&q.back()<=a[i]) {
            q.pop_back();
            id.pop_back();
        }
        id.push_back(i);
        q.push_back(a[i]);
        while(!id.empty()&&id.front()<=i-k) {
            q.pop_front();
            id.pop_front();
        }
        printf("%d ",q.front());
    }
    return 0;
}

by IYSY2009I @ 2023-05-01 15:00:26

@DreamLand_zcb 谢谢大佬