单调队列
单调队列,即队列中元素之间的关系具有单调性,单调递减或单调递增,队首只出队,队尾可入队、出队。
实现方法
1.使用双端队列 Deque 实现
2.使用一个数组和 front、rear 两个指针来实现
- front 指针指向队首元素,rear 指针指向队尾元素,即可实现队首出队与队尾入队、出队操作,如下图所示:
- 由于需要保持单调性,当一个新元素入队时,就需要与队尾元素比较,如果队尾元素大于将入队元素(假设单调递增),则将它从队尾出队,继续重复操作,直到队尾元素小于它,然后将它入队,如下图所示: