Deque单调队列全RE求助

Aw顿顿 @ 2020-11-27 20:30:25

by Aw顿顿 @ 2020-11-27 20:30:32

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct num{
    int val,idx;
}a[1000005];
int n,k;
int maxn[1000005],minn[1000005],top;
void getmax(){
    top=0;
    deque<num>q;
    for(int i=1;i<=n;i++){
        num s=q.back(),t=q.front();
        if(s.idx-t.idx+1==k)q.pop_front();
        while(!q.empty()){
            int x=q.back().val;
            if(a[i].val>=x)q.pop_back();
        }q.push_back(a[i]);
        num tmp=q.front();
        if(i>=k)cout<<tmp.val<<' ';
    }
}void getmin(){
    top=0;
    deque<num>q;
    for(int i=1;i<=n;i++){
        num s=q.back(),t=q.front();
        if(s.idx-t.idx+1==k)q.pop_front();
        while(!q.empty()){
            int x=q.back().val;
            if(a[i].val<=x)q.pop_back();
        }q.push_back(a[i]);
        num tmp=q.front();
        if(i>=k)cout<<tmp.val<<' ';
    }
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].val);
        a[i].idx=i;
    }getmax();getmin();
    return 0;
} 

by Guoyh @ 2020-11-27 20:35:16

 while(!q.empty()){
    int x=q.back().val;
    if(a[i].val<=x)q.pop_back();
}

如果a[i].val <= q.back().val就会死循环

by Guoyh @ 2020-11-27 20:35:39

@Aw顿顿

by M_sea @ 2020-11-27 20:35:51

@Aw顿顿 i=1 时 q 是空的，调用 q.back() 会 RE。

by Aw顿顿 @ 2020-11-27 20:42:28

@Guoyh @M_sea

谢谢/kk

十分感谢