濒临崩溃，需要救助

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-16 09:54:59

不好意思

昨天没看到

蟹蟹dalao

（正在看代码）

by Xfer_splendor @ 2021-07-16 09:55:21

@椋枨

by Xfer_splendor @ 2021-07-16 09:58:24

what‘s the meaning of pair？

by Froranzen @ 2021-07-16 14:21:11

@张子钧 抱歉啊，上午坐车的，没看到（

by Xfer_splendor @ 2021-07-16 14:25:24

没事，问一下pair的用法

by Froranzen @ 2021-07-16 15:00:43

@张子钧 pair 能存两个数值，访问第一个数值的方式是 s.fisrt，访问第二个数值的方式是 s.second，最后存储 pair 的方式的 s.make_pair(第一个值，第二个值)。

by Froranzen @ 2021-07-16 15:02:00

我就是鸽子，别骂了别骂了（

by Froranzen @ 2021-07-16 15:07:12

然后这个题的话，要保证队尾这个 pair 的第二个值 —— 也就是这个 pair 第一个数值的所在位置，必须和当前第 i 个位置的间距小于等于 k 。

by Froranzen @ 2021-07-16 15:10:49

因为如果单看队列中的元素的话，你只知道到现在为止，连续的小于等于 k 个的递增/递减的数值，但不知道这些数值间确切的隔了几个数，所以这里我就用 pair 存下了这些单调的数值的位置，以知道在数列中，这些数值之间的间距。

by Xfer_splendor @ 2021-07-16 15:10:53

会了，蟹蟹dalao @椋枨