单调队列 订阅
单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。 展开全文
单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。
信息
外文名
Monotone queue
属    于
优先队列的一种
基本方程
f[x]=max/min{g(k)}+w[x]
地    位
使用频率不高,但偶尔有重要作用
作    用
1D/1D动态规划等
中文名
单调队列
范    围
限制较多
基于此的算法
基础上改进的斜率优化,单调栈等
代码长度
较短,容易调试
OI/ACM重要性
各种神奇算法的基础
单调队列单调队列的操作
不妨用一个问题来说明单调队列的作用和操作:不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小的元素。最直接的方法:普通队列实现缓存数组。进队出队都是O(1),一次查询需要遍历当前队列的所有元素,故O(n)。堆顶始终是最小元素,故查询是O(1)。而进队出队,都要调整堆,是O(log(n))。RMQ即Range Maximum(Minimum) Query,用来求某个区间内的最大值或最小值。使用线段树或稀疏表是O(log(n))级的。对于这类问题这两种方法也搞得定,但是没有单调队列快。由于单调队列的队头每次一定最小值,故查询为O(1)。进队出队稍微复杂点:进队时,将进队的元素为e,从队尾往前扫描,直到找到一个不大于e的元素d,将e放在d之后,舍弃e之后的所有元素;如果没有找到这样一个d,则将e放在队头(此时队列里只有这一个元素)。出队时,将出队的元素为e,从队头向后扫描,直到找到一个元素f比e后进队,舍弃f之前所有的。(实际操作中,由于是按序逐个出队,所以每次只需要出队只需要比较队头)。每个元素最多进队一次,出队一次,摊排分析下来仍然是 O(1)。上面的话可能还是没能讲出单调队列的核心:队列并不实际存在的,实际存在的是具有单调性的子序列。对这个子序列按心中的队列进行操作,譬如在进队时丢弃的元素,虽然它不存在于这个子序列里,但是还是认为他存在于队列里。另外,进队的顺序和出队的顺序并不一定相同,因为这个队列本身是隐含存在的,可以在进队时看成一个队列,出队时看成另一个队列,只要出队的元素在队列中就行。可以想象成一个队列只有头和身,另一个队列只有身和尾,而这身是共用的。在OI赛场上,大多数题目为单调队列力所不能及的,取而代之的是单调队列基础上改进的斜率优化,单调栈等,因为其限制条件,故潜力不大。但需要掌握,因为有许多算法建立在其基础上。例如斜率优化即为f[i] = min/max{f[j] + g[i] * g[j]},和单调队列尤为相似。单调栈即为单调队列的“栈”版。这两种复杂度也是O(n)的。
收起全文
精华内容
下载资源
问答
  • 单调队列

    2021-04-21 19:12:17
    文章目录前言一、单调队列1.单调队列2.AcWing 154. 滑动窗口题目分析:AC代码二、时间复杂度 前言 复习acwing算法基础课的内容,本篇为讲解基础算法:单调队列,关于时间复杂度:目前博主不太会计算,先鸽了,日后...


    前言

    复习acwing算法基础课的内容,本篇为讲解基础算法:单调队列,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


    一、单调队列

    1.单调队列

    同单调栈一样,在单调队列的元素中,同样也是按照从大到小或是从小到大的顺序进行排列的,有关单调栈,详见博客:单调栈,本博客关于单调队列是用数组模拟队列,如何用数组模拟队列见博客用数组模拟队列,这里不做赘述,关于单调队列的应用和作用,我们由一道题目展开.

    2.AcWing 154. 滑动窗口

    本题链接:滑动窗口
    本博客给出题目截图:

    在这里插入图片描述
    在这里插入图片描述

    题目分析:

    我们用a数组来代表题目中的数组,然后用q数组代表队列,其中q[i]代表的队列中第i - hh+ 1的点在数组a中的下标,比如当hh = 1的时候,i = 3,那么q[3]代表的就是队列里的第三个点在数组a中的下标

    通过样例来进行说明,本题要输出一行最小值和一行最大值,这里拿最小值去距举例:
    1 3 -1 -3 5 3 6 7
    我们可以观察到只要-1存在的话31就不会被输出出去,意味着这两个数是没有意义的,也就是说,当-1被输入进来后,我们可以把31直接删除,具体到队列中,就意味着,如果输入的元素要小于等于队尾元素的话,我们就可以把队尾元素删除,直到队尾元素要小于输入的元素或者队列为空就停止删除操作,这一步的代码为while (tt >= hh && a[q[tt]] >= a[i]) tt --;,同时如果i - k + 1 > q[hh],即队列头的坐标如果不在我们滑动窗口中的时候,我们就让hh ++;,最后说一下输出:当i遍历到第k个点的时候开始输出第一个最小值,因为我们的队列是从坐标0开始的,所以只有当i - 1 >= k的时候我们会开始输出最小值,因为队列中是满足单调递增的,而我们的队列维护的就是滑动窗口的区间,所以对头元素就是我们的最小值,注意对头元素的表示为a[q[hh]]


    AC代码

    #include <cstdio>
    
    using namespace std;
    
    const int N = 1000010;
    
    int q[N], a[N];
    
    int main()
    {
        int n, k;
        int hh = 0, tt = -1;
        scanf ("%d%d", &n, &k);
        
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
        //计算最小值
        for (int i = 0; i < n; i ++ ) 
        {
            while (tt >= hh && a[q[tt]] >= a[i]) tt --;
            q[ ++ tt] = i;
            if (tt >= hh && q[hh] < i - k + 1) hh ++;
            if (i >= k - 1) printf("%d ", a[q[hh]]);
        }
        
        puts("");
        //计算最大值
        tt = -1, hh = 0;                    //这里一定要注意重新更新 hh 和 tt
        for (int i = 0; i < n; i ++ )
        {
            while (tt >= hh && a[q[tt]] <= a[i]) tt --;
            q[ ++ tt] = i;
            if (tt >= hh && q[hh] < i - k + 1) hh ++;
            if (i >= k - 1) printf("%d ", a[q[hh]]);
        }
        
        return 0;
    }
    

    二、时间复杂度

    关于单调队列的各操作时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,578
精华内容 14,631
关键字:

单调队列