单调队列,有一点疑问求助

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

Moyyer_suiy @ 2022-10-11 19:26:37

#include<bits/stdc++.h>
const int N = 1000010;
using namespace std;
int n, k, a;
struct s{
    int v, num;
};
deque <s> q1, q2;
int ans1[N], ans2[N];

int main(){
    cin>> n>> k;
    s q;
    for(int i = 1; i <= n; i ++){
        cin>> a;
        q.v = a;
        q.num = i;

        while(!q1.empty() && a <= q1.back().v) q1.pop_back();
        q1.push_back(q);
        if(q1.front().num + k <= i) q1.pop_front();

        while(!q2.empty() && a >= q2.back().v) q2.pop_back();
        q2.push_back(q);
        if(q2.front().num + k <= i) q2.pop_front();

        if(i >= k){
            ans1[i - k + 1] = q1.front().v;
            ans2[i - k + 1] = q2.front().v;
        }
    }
    for(int i = 1; i <= n - k + 1; i ++) cout<< ans1[i]<<" ";
    cout<< endl;
    for(int i = 1; i <= n - k + 1; i ++) cout<< ans2[i]<<" ";
    return 0;
}

用双端队列做的,写着写着有点不太理解,为什么21和22行,以及25和26行不能换一下前后顺序,即为什么不可以先把滑出窗口的弹出去然后再将新元素压进来呢?

上面贴的这个代码是对的,然后换一下顺序就不对了,脑子有点绕不过弯不是特别能理解,来求大佬解释一下谢谢!


by Error_Eric @ 2022-10-11 19:33:34

若交换顺序有可能把队列 pop 成空的,此时 q1.front() 会报错。如果先 push 就不能出现这种情况因为刚加进去的不会被 pop 掉。

如果交换兴许改成 (!q1.empty())&&(q1.front().num + k <= i) 就可以了。

这个小细节在你以后的 OI 生涯中大概率会多次遇到。


by Error_Eric @ 2022-10-11 19:33:56

@茉小窈儿


by DeusExMachina @ 2022-10-11 19:34:11

@茉小窈儿 有没有一种可能,pop 着 pop 着连 front 都没有了


by Moyyer_suiy @ 2022-10-12 16:59:23

@Error_Eric 好的谢谢!改后就可以了


|