# 特殊数据结构：单调队列
相关推荐：
* [几个反直觉的概率问题](https://labuladong.gitee.io/algo/)
* [Git/SQL/正则表达式的在线练习平台](https://labuladong.gitee.io/algo/)
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
[239.滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum)
**-----------**
前文讲了一种特殊的数据结构「单调栈」monotonic stack，解决了一类问题「Next Greater Number」，本文写一个类似的数据结构「单调队列」。
也许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素单调递增（或递减）。这个数据结构有什么用？可以解决滑动窗口的一系列问题。
看一道 LeetCode 题目，难度 hard：
### 一、搭建解题框架
这道题不复杂，难点在于如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。在之前我们探讨过类似的场景，得到一个结论：
在一堆数字中，已知最值，如果给这堆数添加一个数，那么比较一下就可以很快算出最值；但如果减少一个数，就不一定能很快得到最值了，而要遍历所有数重新找最值。
回到这道题的场景，每个窗口前进的时候，要添加一个数同时减少一个数，所以想在 O(1) 的时间得出新的最值，就需要「单调队列」这种特殊的数据结构来辅助了。
一个普通的队列一定有这两个操作：
```java
class Queue {
void push(int n);
// 或 enqueue，在队尾加入元素 n
void pop();
// 或 dequeue，删除队头元素
}
```
一个「单调队列」的操作也差不多：
```java
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
```
当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：
```cpp
vector maxSlidingWindow(vector& nums, int k) {
MonotonicQueue window;
vector res;
for (int i = 0; i < nums.size(); i++) {
if (i < k - 1) { //先把窗口的前 k - 1 填满
window.push(nums[i]);
} else { // 窗口开始向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k + 1]);
// nums[i - k + 1] 就是窗口最后的元素
}
}
return res;
}
```
这个思路很简单，能理解吧？下面我们开始重头戏，单调队列的实现。
### 二、实现单调队列数据结构
首先我们要认识另一种数据结构：deque，即双端队列。很简单：
```java
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();
}
```
而且，这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构，用链表作为底层结构的话，很容易实现这些功能。
「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素，但是要把前面比新元素小的元素都删掉：
```cpp
class MonotonicQueue {
private:
deque data;
public:
void push(int n) {
while (!data.empty() && data.back() < n)
data.pop_back();
data.push_back(n);
}
};
```
你可以想象，加入数字的大小代表人的体重，把前面体重不足的都压扁了，直到遇到更大的量级才停住。
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max() API 可以可以这样写：
```cpp
int max() {
return data.front();
}
```
pop() API 在队头删除元素 n，也很好写：
```cpp
void pop(int n) {
if (!data.empty() && data.front() == n)
data.pop_front();
}
```
之所以要判断 `data.front() == n`，是因为我们想删除的队头元素 n 可能已经被「压扁」了，这时候就不用删除了：
至此，单调队列设计完毕，看下完整的解题代码：
```cpp
class MonotonicQueue {
private:
deque data;
public:
void push(int n) {
while (!data.empty() && data.back() < n)
data.pop_back();
data.push_back(n);
}
int max() { return data.front(); }
void pop(int n) {
if (!data.empty() && data.front() == n)
data.pop_front();
}
};
vector maxSlidingWindow(vector& nums, int k) {
MonotonicQueue window;
vector res;
for (int i = 0; i < nums.size(); i++) {
if (i < k - 1) { //先填满窗口的前 k - 1
window.push(nums[i]);
} else { // 窗口向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k + 1]);
}
}
return res;
}
```
**三、算法复杂度分析**
读者可能疑惑，push 操作中含有 while 循环，时间复杂度不是 O(1) 呀，那么本算法的时间复杂度应该不是线性时间吧？
单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push_back 和 pop_back 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。
空间复杂度就很简单了，就是窗口的大小 O(k)。
**四、最后总结**
有的读者可能觉得「单调队列」和「优先级队列」比较像，实际上差别很大的。
单调队列在添加元素的时候靠删除元素保持队列的单调性，相当于抽取出某个函数中单调递增（或递减）的部分；而优先级队列（二叉堆）相当于自动排序，差别大了去了。
赶紧去拿下 LeetCode 第 239 道题吧～
**＿＿＿＿＿＿＿＿＿＿＿＿＿**
**刷算法，学套路，认准 labuladong，公众号和 [在线电子书](https://labuladong.gitee.io/algo/) 持续更新最新文章**。
**本小抄即将出版，微信扫码关注公众号，后台回复「小抄」限时免费获取，回复「进群」可进刷题群一起刷题，带你搞定 LeetCode**。
======其他语言代码======
[239.滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum)
### python
由[SCUHZS](ttps://github.com/brucecat)提供
```python
from collections import deque
class MonotonicQueue(object):
def __init__(self):
# 双端队列
self.data = deque()
def push(self, n):
# 实现单调队列的push方法
while self.data and self.data[-1] < n:
self.data.pop()
self.data.append(n)
def max(self):
# 取得单调队列中的最大值
return self.data[0]
def pop(self, n):
# 实现单调队列的pop方法
if self.data and self.data[0] == n:
self.data.popleft()
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 单调队列实现的窗口
window = MonotonicQueue()
# 结果
res = []
for i in range(0, len(nums)):
if i < k-1:
# 先填满窗口前k-1
window.push(nums[i])
else:
# 窗口向前滑动
window.push(nums[i])
res.append(window.max())
window.pop(nums[i-k+1])
return res
```
### java
```java
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 判断数组或者窗口长度为0的情况
if (len * k == 0) {
return new int[0];
}
/*
采用两端扫描的方法
将数组分成大小为 k 的若干个窗口, 对每个窗口分别从左往右和从右往左扫描, 记录扫描的最大值
left[] 记录从左往右扫描的最大值
right[] 记录从右往左扫描的最大值
*/
int[] left = new int[len];
int[] right = new int[len];
for (int i = 0; i < len; i = i + k) {
// 每个窗口中的第一个值
left[i] = nums[i];
// 窗口的最后边界
int index = i + k - 1 >= len ? len - 1 : i + k - 1;
// 每个窗口的最后一个值
right[index] = nums[index];
// 对该窗口从左往右扫描
for (int j = i + 1; j <= index; j++) {
left[j] = Math.max(left[j - 1], nums[j]);
}
// 对该窗口从右往左扫描
for (int j = index - 1; j >= i; j--) {
right[j] = Math.max(right[j + 1], nums[j]);
}
}
int[] arr = new int[len - k + 1];
// 对于第 i 个位置, 它一定是该窗口从右往左扫描数组中的最后一个值, 相对的 i + k - 1 是该窗口从左向右扫描数组中的最后一个位置
// 对两者取最大值即可
for (int i = 0; i < len - k + 1; i++) {
arr[i] = Math.max(right[i], left[i + k - 1]);
}
return arr;
}
}
```
### javascript
这里用js实现的思路和上文中一样，都是自己实现一个单调队列，注意，这里的单调队列和优先级队列（大小堆）不是同一个概念。
```js
let MonotonicQueue = function () {
// 模拟一个deque双端队列
this.data = [];
// 在队尾添加元素 n
this.push = function (n) {
while (this.data.length !== 0 && this.data[this.data.length - 1] < n)
this.data.pop();
this.data.push(n);
}
// 返回当前队列中的最大值
this.max = function () {
return this.data[0];
};
// 队头元素如果是 n，删除它
this.pop = function (n) {
if (this.data.length !== 0 && this.data[0] === n)
this.data.shift();
};
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let window = new MonotonicQueue();
let res = []
for (let i = 0; i < nums.length; i++) {
if (i < k - 1) { //先把窗口的前 k - 1 填满
window.push(nums[i]);
} else {
// 窗口开始向前滑动
window.push(nums[i]);
res.push(window.max());
window.pop(nums[i - k + 1]);
// nums[i - k + 1] 就是窗口最后的元素
}
}
return res;
};
```
