单调队列
单调队列,即队列中元素之间的关系具有单调性,单调递减或单调递增,队首只出队,队尾可入队、出队。
![](https://ucc.alicdn.com/images/user-upload-01/b29c81b2b3764ef190a7a4ad2adef74e.png?x-oss-process=image/resize,w_1400/format,webp)
![](https://ucc.alicdn.com/images/user-upload-01/bfc7cc6075e04a7c827194f6c59c9595.png?x-oss-process=image/resize,w_1400/format,webp)
实现方法
1.使用双端队列 Deque 实现
2.使用一个数组和 front、rear 两个指针来实现
- front 指针指向队首元素,rear 指针指向队尾元素,即可实现队首出队与队尾入队、出队操作,如下图所示:
![](https://ucc.alicdn.com/images/user-upload-01/51161321506340d484e5c11fa2f02fbf.png?x-oss-process=image/resize,w_1400/format,webp)
- 由于需要保持单调性,当一个新元素入队时,就需要与队尾元素比较,如果队尾元素大于将入队元素(假设单调递增),则将它从队尾出队,继续重复操作,直到队尾元素小于它,然后将它入队,如下图所示:
![](https://ucc.alicdn.com/images/user-upload-01/fa1c939508d442b7ba8f376d24861196.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQWN4Nw==,size_20,color_FFFFFF,t_70,g_se,x_16&x-oss-process=image/resize,w_1400/format,webp)