Assignment(单调队列)

做题时的问题:

两个单调队列实现会出现一个问题:可用范围因最大最小值队列(存在队头)的更改(出队,导致不可见)而缩小。如果单纯计算队列中覆盖的范围,就会漏掉一些区间。如这组数据:

1
10 5
0 3 4 5 2 1 6 7 8 9 

当运行到数字“2”处时,单调队列(存下标)变成这样:

大:4 5

小:5

实际上,在2~5范围内的所有区间均有效。

(以上只是反思本蒟蒻的个人问题,大佬可无视)

    ---------------分割线---------------

思路:

需要两个标记:当前有效范围的左端点j(当队头元素差>=k时改变)和右端点i(随循环进行)。【为方便计算,我开成左开右闭的(j,i]】

当队头元素差>=k时,将j右移一位,并把处于有效范围外的元素从头部出队。操作完后,累加答案。

for(i=1;i<=n;++i)//带min的与区间最小值有关,max最大值
{
    while(lmin<=rmin&&a[i]<a[qmin[rmin]]) qmin[rmin--]=0;//删除,方便调试
    qmin[++rmin]=i;
    while(lmax<=rmax&&a[i]>a[qmax[rmax]]) qmax[rmax--]=0;
    qmax[++rmax]=i;
    while(lmin<=rmin&&lmax<=rmax
    &&a[qmax[lmax]]-a[qmin[lmin]]>=k)
    {
        ++j;//更改有效范围
        if (qmax[lmax]==j)
            qmax[lmax++]=0;
        if (qmin[lmin]==j)
            qmin[lmin++]=0;//把无用最大最小值出队
    }
    ans+=i-j;//累加答案
}

 

原文地址:https://www.cnblogs.com/xzs123456/p/10803206.html