滑动窗口求条

P1886 滑动窗口 /【模板】单调队列

xuyunlong120820 @ 2024-08-30 09:59:42

#include <bits/stdc++.h>
using namespace std;
long long n,k;
long long a[1000005];
long long maxn=LLONG_MIN,maxi,minn=LLONG_MAX,mini;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    scanf("%lld %lld",&n,&k);
    for(int i=1; i<=n; i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1; i<=n-k+1; i++){
        if(mini>n){
            break;
        }
        if(mini<i){
            minn=min(a[i],min(a[i+1],a[i+2]));
            if(minn=a[i+2]){
                mini=i+2;
            }else if(minn=a[i+1]){
                mini=i+1;
            }else{
                mini=i;
            }
            cout<<minn<<" ";
            continue;
        }
        if(mini>n){
            break;
        }
        if(minn>a[i]){
            minn=a[i];
            mini=i;
        }
        cout<<minn<<" ";
    }
    cout<<"\n";
    for(int i=1; i<=n-k+1; i++){
        if(maxi>n){
            break;
        }
        if(maxi<i){
            maxn=max(a[i],max(a[i+1],a[i+2]));
            if(maxn=a[i+2]){
                maxi=i+2;
            }else if(maxn=a[i+1]){
                maxi=i+1;
            }else{
                maxi=i;
            }
            cout<<maxn<<" ";
            continue;
        }
        if(maxi>n){
            break;
        }
        if(maxn<a[i]){
            maxn=a[i];
            maxi=i;
        }
        cout<<maxn<<" ";
    }
    cout<<"\n";
    return 0;
}

调不对力（大悲）

by LSC_IS_SB @ 2024-08-30 10:13:47

题目中说一个大小为 k的窗口，谁跟你说大小一定为3

by xuyunlong120820 @ 2024-08-30 10:15:55

@zhenguo 我不是n-k+1吗

by liuying_QAQ @ 2024-08-30 10:21:37

但是你写的是minn=min(a[i],min(a[i+1],a[i+2])); 就相当于只算了三个

by LSC_IS_SB @ 2024-08-30 10:29:04


#include<bits/stdc++.h>
using namespace std;

deque<int>q;
deque<int>dq;//创建双向队列，q存最大值编号，dq存最小值编号
long long n,a[1000010],k,p[1000010],dp[1000010],t;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        while(!q.empty()&&a[i]>a[q.back()])q.pop_back();//如果新的值比原来右侧的值大，就把右侧的值弹出队列

while(!dq.empty()&&a[i]<a[dq.back()])dq.pop_back();//如果新的值比原来右侧的值小，就把右侧的值弹出队列
        q.push_back(i);
        dq.push_back(i);                                                     //在右侧加入编号
        while(q.front()<=i-k)q.pop_front();
        while(dq.front()<=i-k)dq.pop_front();
        //若左侧的编号已经不在窗口之中，就直接弹出
        p[i]=a[q.front()];
        dp[i]=a[dq.front()];
        //记录答案
    }

    for(int i=k;i<=n;i++){
        cout<<dp[i]<<" ";
    }

    cout<<"\n";

    for(int i=k;i<=n;i++){
        cout<<p[i]<<" ";
    }
    //输出
    return 0;
}

by xuyunlong120820 @ 2024-08-30 10:31:46

@wangzixin_123 @zhenguo 感谢，已回关

|