单调队列,WA第七点。。。。求助

P1440 求m区间内的最小值

syyyyhy @ 2022-04-05 19:18:55

#include <bits/stdc++.h>
using namespace std;

int n,m;
int stake[2000020];
int num[2000020];
int main()
{
    cin>>n>>m;
    int h=0;
    int t=-1;
    printf("0\n");
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    for(int i=1;i<=n-1;i++)
    {
        int l=i-m+1;
        if(stake[h]<l)
        {
            h++;
        }
        while(num[stake[t]]>num[i]&&h<=t)
        {
            t--;
        }
        t++;
        stake[t]=i;
        printf("%d\n",num[stake[h]]);
    }
    return 0;
} 

by Refined_heart @ 2022-04-05 19:49:35

@syy1091906233 似乎空间越界了

移动 h,t 的时候要判断队列是不是空的


by syyyyhy @ 2022-04-05 20:59:29

@Refined_heart 谢谢大佬!!确实是这个原因!我加上if(h<=t&&stake[h]<l),判断不为空之后就AC了


|