濒临崩溃，需要救助

Xfer_splendor @ 2021-07-15 16:35:13

#include<iostream>
#include<queue>
using namespace std;
int n,k,a[100001];
deque<int>s;
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front()<=a[i]){
            s.pop_front();
        }
        s.push_front(a[i]);
        while (s.size()>k){
            s.pop_back();
        }
        if (i>=k){
            cout<<s.back()<<" ";
        }
    }
    cout<<endl;
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front()>=a[i]){
            s.pop_front();
        }
        s.push_front(a[i]);
        while (s.size()>k){
            s.pop_back();
        }
        if (i>=k){
            cout<<s.back()<<" ";
        }
    }
    return 0;
}

by Xfer_splendor @ 2021-07-15 16:40:15

带注释的

#include<iostream>
#include<queue>
using namespace std;
int n,k,a[100001];
deque<int>s;//双向队列 
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>a[i];//输入 
    }
    //max 
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front()<=a[i]){
            s.pop_front();//删除比它小的 
        }
        s.push_front(a[i]);//压入这个元素 
        while (s.size()>k){
            s.pop_back();//删掉多余的 
        }
        if (i>=k){
            cout<<s.back()<<" ";//输出 
        }
    }
    cout<<endl;
    //min 
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front()>=a[i]){
            s.pop_front();//删除比它大的 
        }
        s.push_front(a[i]);
        while (s.size()>k){
            s.pop_back();//删掉多余的 
        }
        if (i>=k){
            cout<<s.back()<<" ";//输出
        }
    }
    return 0;
}

by wwy06716 @ 2021-07-15 17:22:30

虽然很想帮你，但我看不懂你的程序

by Rosemary_dream @ 2021-07-15 17:33:41

那个题啊？

by Froranzen @ 2021-07-15 18:00:13

但凡你不写 deque 都不至于这样。

by Froranzen @ 2021-07-15 18:00:48

你写 deque 的话区间长度不好判断的……

by Froranzen @ 2021-07-15 18:01:05

我试着改改吧

by Froranzen @ 2021-07-15 18:13:43

为啥会 50 ……

by Froranzen @ 2021-07-15 18:15:45

草，兄弟，你的数组开小了。

by Froranzen @ 2021-07-15 18:16:30

代码在这里，不懂地方的问我。

#include<iostream>
#include<queue>
using namespace std;
int n,k,a[1000003];
deque< pair <int, int> >s;
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front().first>=a[i]){
            s.pop_front();
        }
        s.push_front(make_pair(a[i], i));
        while (i - s.back().second + 1 > k && s.size()){
            s.pop_back();
        }
        if (i>=k){
            cout<<s.back().first<<" ";
        }
    }
    cout<<endl;
    while(!s.empty()) s.pop_front();
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.front().first<=a[i]){
            s.pop_front();
        }
        s.push_front(make_pair(a[i], i));
        while (i - s.back().second + 1 > k && s.size()){
            s.pop_back();
        }
        if (i>=k){
            cout<<s.back().first<<" ";
        }
    }
    return 0;
}

by Froranzen @ 2021-07-15 18:19:44

y1s1，跑得是真慢（