首页 > 其他分享 >单调队列——本质上和单调栈是一样的思路

单调队列——本质上和单调栈是一样的思路

时间:2022-12-16 20:45:51浏览次数:50  
标签:队列 新生 back 选手 栈是 区间 单调

算法学习笔记(66): 单调队列

https://zhuanlan.zhihu.com/p/346354943

“如果一个选手比你小还比你强,你就可以退役了。”——单调队列的原理

好久没写笔记了,先补一个简单的。单调队列是一种主要用于解决滑动窗口类问题的数据结构,即,在长度为 n 的序列中,求每个长度为 m 的区间的区间最值。它的时间复杂度是 O(n) ,在这个问题中比 O(nlog⁡n) 的ST表线段树要优。

单调队列的基本思想是,维护一个双向队列(deque),遍历序列,仅当一个元素可能成为某个区间最值时才保留它。

形象地打个比方,上面的序列可以看成学校里各个年级XCPC选手,数字越大代表能力越强。每个选手只能在大学四年间参赛,毕业了就没有机会了。那么,每一年的王牌选手都在哪个年级呢?

一开始的时候,大三大四的学长都比较菜,大二的最强,而大一的等大二的毕业后还有机会上位,所以队列里有两个数。

一年过去了,原本大一的成为大二,却发现新进校的新生非常强,自己再也没有机会成为最大值了,所以弹出队列。

又过了一年,新入校的新生尽管能力只有1,但理论上只要后面的人比他还菜,还是可能成为区间最大值的,所以入队。

终于,原本的王牌毕业了,后面的人以为熬出头了,谁知道这时一个巨佬级别的新生进入了集训队,这下其他所有人都没机会了。

(这只是比方,现实中各位选手的实力是会增长的,不符合这个模型ovo)

总之,观察就会发现,我们维护的这个队列总是单调递减的。如果维护区间最小值,那么维护的队列就是单调递增的。这就是为什么叫单调队列。

代码也很简洁:

deque<int> Q; // 存储的是编号
for (int i = 0; i < n; ++i)
{
    if (!Q.empty() && i - Q.front() >= m) // 毕业
        Q.pop_front();
    while (!Q.empty() && V[Q.back()] < V[i]) // 比新生弱的当场退役(求区间最小值把这里改成>即可)
        Q.pop_back();
    Q.push_back(i); // 新生入队
    if (i >= m - 1)
        cout << V[Q.front()] << " ";
}

标签:队列,新生,back,选手,栈是,区间,单调
From: https://www.cnblogs.com/bonelee/p/16988251.html

相关文章

  • java集合类——Stack栈类与Queue队列
      今日走读代码时,遇到stack栈类,特查看java的API文档,总结如下:Stack继承Vector类,它通过五个操作对类Vector进行了扩展。栈是后进先出的。栈提供了通常的push和pop......
  • 【LeeCode】栈和队列
    ​​学习参考​​【栈】importjava.util.*;//2022-12-15//栈:先进后出classMyStack{publicint[]elem;publicintuseSize;publicMyStack(){this......
  • 微信协议简单调研笔记
    前言微信可调研点很多,这里仅仅从协议角度进行调研,会涉及到微信协议交换、消息收发等。所谓“弱水三千,只取一瓢”吧。杂七杂八的,有些长,可直接拉到最后看结论好了。一。微信协......
  • [EER1]单调栈
    链接:https://www.luogu.com.cn/problem/P6198题目描述:给定一个长为\(n\)数列\(S\),求一个字典序最小的排列,使得将这个排列依次放入单调栈中序列中元素的个数与\(S\)一一对......
  • spring boot + Redis实现消息队列-生产消费者
    实现思路:Redis本身提供了一个发布/订阅模式,但生产消费者模式需要我们自己去实现。利用Redis中的队列,将新消息放入名称为xx的队列末尾,完成消息生产者。启动一个线程,使用​​b......
  • 第一百一十三篇: JS数组Array(二)数组方法 栈、队列、排序
    好家伙,  在上一篇中,我们知道了,JS的数组中每个槽位可以存储任意类型的数据那么,我们能通过数组去模仿某些数据结构吗?答案是肯定的 1.栈方法ECMAScript给数组......
  • 剑指Offer-Java-用两个栈实现队列
    题目用两个栈来实现一个队列,完成队列的Push和Pop操作。队列中的元素为int类型。代码只需要来回倒就可以实现了。importjava.util.Stack;publicclassSolution{Stack......
  • rabbitMQ交换机,路由键,队列配置
    交换机是直连交换机:先建好交换机,把对应的【队列】通过【路由键】与【交换机】绑定。  队列配置:给队列配置路由键,死信队列 ......
  • 使用redis做消息队列mq的总结
    总结目前使用redis做消息队列的的方式有3中,list,    publish/subscribe,    streamlist做mq的总结使用方法1.生产者可以lpush写入消息,消费者可以rpop读取......
  • 常用队列系统设计,通用his就诊叫号抢号模式,通用his体检叫号自动分配模式
    2022年12月12日14:03:33通用his就诊叫号抢号模式流程说明:患者挂号之后,到就诊科室区域,在护士站刷卡,进入队列,等到叫号屏排队,医生看完当前病人之后,点击叫号软件,从科室队列获......