备案控制台
开发者社区 云计算 文章 正文

浅谈单调队列

2022-04-25 122
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单调队列的实现方法

单调队列


  单调队列，即队列中元素之间的关系具有单调性，单调递减或单调递增，队首只出队，队尾可入队、出队。


实现方法


1.使用双端队列 Deque 实现

2.使用一个数组和 front、rear 两个指针来实现


  • front 指针指向队首元素，rear 指针指向队尾元素，即可实现队首出队与队尾入队、出队操作，如下图所示：



  • 由于需要保持单调性，当一个新元素入队时，就需要与队尾元素比较，如果队尾元素大于将入队元素(假设单调递增)，则将它从队尾出队，继续重复操作，直到队尾元素小于它，然后将它入队，如下图所示：



游客q7aiz7vku45zk
目录
相关文章
我也要当昏君
|
11天前
|
NoSQL 容器 消息中间件
单调栈、单调队列
单调栈、单调队列
我也要当昏君
25 0
什么时候能躺平
|
2天前
|
算法 C++
c++算法学习笔记 (15) 单调栈与单调队列
c++算法学习笔记 (15) 单调栈与单调队列
什么时候能躺平
8 2
阿里云Forward
|
11天前
|
算法 前端开发
详解双端队列&单调队列
详解双端队列&单调队列
阿里云Forward
72 0
闻缺陷则喜何志丹
|
11天前
|
算法 测试技术 C#
【单调队列】LeetCode1425:带限制的子序列和
【单调队列】LeetCode1425:带限制的子序列和
闻缺陷则喜何志丹
29 0
【单调队列】LeetCode1425:带限制的子序列和
得过且过的勇者y
|
11天前
LeetCode刷题Day11——栈和队列（逆波兰表达式、优先队列、单调队列）
一、逆波兰表达式求值
得过且过的勇者y
23 0
Hayaizo
|
9月前
滑动窗口(单调队列)
滑动窗口(单调队列)
Hayaizo
29 0
ZhangBlossom
|
10月前
|
算法 测试技术
【算法】单调栈问题
【算法】单调栈问题
ZhangBlossom
41 0
pandaconda
|
11月前
|
C++
剑指offer 53. 数组中的逆序对
剑指offer 53. 数组中的逆序对
pandaconda
59 0
剑指offer 53. 数组中的逆序对
让线程再跑一会
|
Java
洛谷（2947）向右看齐-单调栈-链表
单调栈对新手来说不好理解，但链表就特别简单，但在有时间限制的竞赛中，很容易超时，因此如果实在要使用链表，注意使用链表的类型，Java提供的两种实现链表的方式
让线程再跑一会
71 0
timerring
|
人工智能 算法
单调队列算法模板及应用
单调队列算法模板及应用
timerring
72 0