浅谈单调队列

简介: 单调队列的实现方法

单调队列


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


实现方法


1.使用双端队列 Deque 实现

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


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



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



相关文章
|
6月前
|
NoSQL 容器 消息中间件
单调栈、单调队列
单调栈、单调队列
|
算法
【算法专题突破】双指针 - 三数之和(7)
【算法专题突破】双指针 - 三数之和(7)
47 0
|
1月前
|
算法 C++
单调队列(C/C++)
单调队列(C/C++)
|
1月前
|
算法 C++
|
6月前
|
算法 C++
c++算法学习笔记 (15) 单调栈与单调队列
c++算法学习笔记 (15) 单调栈与单调队列
|
6月前
|
算法 测试技术 C#
【单调队列】LeetCode1425:带限制的子序列和
【单调队列】LeetCode1425:带限制的子序列和
【单调队列】LeetCode1425:带限制的子序列和
|
6月前
|
算法 前端开发
详解双端队列&单调队列
详解双端队列&单调队列
|
算法
【算法专题突破】双指针 - 四数之和(8)
【算法专题突破】双指针 - 四数之和(8)
31 0
|
算法 测试技术
【算法】单调栈问题
【算法】单调栈问题
65 0