单调队列 就是⼀个「队列」，只是使⽤了⼀点巧妙的⽅法，使得队列中的元素单调递增（或递减）。这个数据结构有什么⽤？可以解决滑动窗⼝的⼀系列问题。
每个窗⼝前进的时候，要添加⼀个数同时减少⼀个数，所以想在 O(1) 的时间得出新的最值，就需要「单调队列」这种特殊的数据结构来辅助了。
⼀个「单调队列」的操作：
1
2
3
4
5
6
7
8
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最⼤值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
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
35
36
37
static int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) { //先填满窗⼝的前 k - 1
window.push(nums[i]);
} else { // 窗⼝向前滑动
window.push(nums[i]);
res[i - k + 1] = window.max();
window.pop(nums[i - k + 1]);
}
}
return res;
}
public static class MonotonicQueue {
private Deque<Integer> data = new ArrayDeque<>();
public void push(int n) {
while (!data.isEmpty() && data.peekLast() < n) {
data.pollLast();
}
data.addLast(n);
}
int max() {
return data.peekFirst();
}
void pop(int n) {
if (!data.isEmpty() && data.peekFirst() == n)
data.pollFirst();
}
}
单调队列的 push ⽅法在队尾添加元素，但是要把前⾯⽐新元素⼩的元素都删掉：
单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push_back 和 pop_back ⼀次，没有任何多余操作，所以整体的复杂度还是 O(N)。
空间复杂度就很简单了，就是窗⼝的⼤⼩ O(k)。
