*“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理 *
介绍
单调队列的基本思想是，维护一个双向队列（deque），遍历序列，仅当一个元素可能成为某个区间最值时才保留它。
设计单调队列的时候，pop，和 push 操作要保持如下规则：
- pop(value)：如果窗口移除的元素 value 等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果 push 的元素 value 大于入口元素的数值，那么就将队列入口的元素弹出，直到 push 元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问 que.front() 就可以返回当前窗口的最大值。
以题目示例为例，输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：
实现
保证队列里单调递减或递增的原则，所以叫做单调队列。
以下不是固定写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| type MonotoneQueue struct {
queue []int
}
func Constructor() MonotoneQueue {
return MonotoneQueue{
queue: make([]int, 0),
}
}
func (this *MonotoneQueue) Front() int {
return this.queue[0]
}
func (this *MonotoneQueue) Back() int {
return this.queue[len(this.queue)-1]
}
func (this *MonotoneQueue) Empty() bool {
return len(this.queue) == 0
}
func (this *MonotoneQueue) Push(x int) {
for !this.Empty() && x > this.Back() {
this.queue = this.queue[:len(this.queue)-1]
}
this.queue = append(this.queue, x)
}
func (this *MonotoneQueue) Pop(x int) {
if !this.Empty() && this.Front() == x {
this.queue = this.queue[1:]
}
}
|