求助!!用STL过了,数组模拟队列没过.

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

PPXppx @ 2018-12-22 16:20:04

    int l=1,r=1;q[1]=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&q[l]<i-k)l++;
        ans1[i]=max(a[q[l]],a[i]);
        while(l<=r&&a[i]>=a[q[r]])r--;
        q[++r]=i;
    }//最大值
    l=1,r=1;Q[1]=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&Q[l]<i-k)l++;
        ans2[i]=min(a[Q[l]],a[i]);
        while(l<=r&&a[i]<=a[Q[r]])r--;
        Q[++r]=i;
    }//最小值

|