单调队列·求助

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

_Glassy_Sky_ @ 2023-01-13 21:24:46

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct node
{
    int num, id;
}que[maxn];
int head = 1, tail = 0;
int a[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        while(head <= tail && que[head].id + k > i)
            head ++;
        while(head <= tail && que[tail].num > a[i])
            tail --;
        que[++ tail].id = i;
        que[tail].num = a[i]; 
        if(i >= k)
            printf("%d ", que[head].num);
    }
    head = 1, tail = 0;
    cout << "\n";
    for(int i = 1; i <= n; i ++)
    {
        while(head <= tail && que[head].id + k <= i)
            head ++;
        while(head <= tail && que[tail].num <= a[i])
            tail --;
        que[++ tail].id = i;
        que[tail].num = a[i]; 
        if(i >= k)
            printf("%d ", que[head].num);
    }
    return 0;
}

by _l_l_ @ 2023-01-13 21:40:38

@FZwangmuem 第一次单调队列的第一个 while 第二个判断条件是 <=


by _Glassy_Sky_ @ 2023-01-14 14:08:14

@_ll 谢谢大佬,已经过了


|