单调队列.md

# 特殊数据结构：单调队列

<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.github.io/algo/images/souyisou1.png)

**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0；[第 13 期刷题打卡](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 最后一天报名！另外，建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章，体验更好。**



读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) | [239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/) | 🔴
| - | [剑指 Offer 59 - I. 滑动窗口的最大值](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/) | 🔴
| - | [剑指 Offer 59 - II. 队列的最大值](https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/) | 🟠

**-----------**

前文用 [单调栈解决三道算法问题](https://labuladong.github.io/article/fname.html?fname=单调栈) 介绍了单调栈这种特殊数据结构，本文写一个类似的数据结构「单调队列」。

也许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。

为啥要发明「单调队列」这种结构呢，主要是为了解决下面这个场景：

**给你一个数组 `window`，已知其最值为 `A`，如果给 `window` 中添加一个数 `B`，那么比较一下 `A` 和 `B` 就可以立即算出新的最值；但如果要从 `window` 数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是 `A`，就需要遍历 `window` 中的所有元素重新寻找新的最值**。

这个场景很常见，但不用单调队列似乎也可以，比如优先级队列也是一种特殊的队列，专门用来动态寻找最值的，我创建一个大（小）顶堆，不就可以很快拿到最大（小）值了吗？

如果单纯地维护最值的话，优先级队列很专业，队头元素就是最值。但优先级队列无法满足标准队列结构「先进先出」的**时间顺序**，因为优先级队列底层利用二叉堆对元素进行动态排序，元素的出队顺序是元素的大小顺序，和入队的先后顺序完全没有关系。

所以，现在需要一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。

「单调队列」这个数据结构主要用来辅助解决滑动窗口相关的问题，前文 [滑动窗口核心框架](https://labuladong.github.io/article/fname.html?fname=滑动窗口技巧进阶) 把滑动窗口算法作为双指针技巧的一部分进行了讲解，但有些稍微复杂的滑动窗口问题不能只靠两个指针来解决，需要上更先进的数据结构。

比方说，你注意看前文 [滑动窗口核心框架](https://labuladong.github.io/article/fname.html?fname=滑动窗口技巧进阶) 讲的几道题目，每当窗口扩大（`right++`）和窗口缩小（`left++`）时，你单凭移出和移入窗口的元素即可决定是否更新答案。

但就本文开头说的那个判断一个窗口中最值的例子，你就无法单凭移出窗口的那个元素更新窗口的最值，除非重新遍历所有元素，但这样的话时间复杂度就上来了，这是我们不希望看到的。

我们来看看力扣第 239 题「滑动窗口最大值」，就是一道标准的滑动窗口问题：

给你输入一个数组 `nums` 和一个正整数 `k`，有一个大小为 `k` 的窗口在 `nums` 上从左至右滑动，请你输出每次窗口中 `k` 个元素的最大值。

函数签名如下：

```java
int[] maxSlidingWindow(int[] nums, int k);
```

比如说力扣给出的一个示例：

![](https://labuladong.github.io/algo/images/单调队列/window.png)

接下来，我们就借助单调队列结构，用 `O(1)` 时间算出每个滑动窗口中的最大值，使得整个算法在线性时间完成。

### 一、搭建解题框架

在介绍「单调队列」这种数据结构的 API 之前，先来看看一个普通的队列的标准 API：

```java
class Queue {
    // enqueue 操作，在队尾加入元素 n
    void push(int n);
    // dequeue 操作，删除队头元素
    void pop();
}
```

我们要实现的「单调队列」的 API 也差不多：

```java
class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n，删除它
    void pop(int n);
}
```

当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：

```java
int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List<Integer> res = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先把窗口的前 k - 1 填满
            window.push(nums[i]);
        } else {
            // 窗口开始向前滑动
            // 移入新元素
            window.push(nums[i]);
            // 将当前窗口中的最大元素记入结果
            res.add(window.max());
            // 移出最后的元素
            window.pop(nums[i - k + 1]);
        }
    }
    // 将 List 类型转化成 int[] 数组作为返回值
    int[] arr = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        arr[i] = res.get(i);
    }
    return arr;
}
```

![](https://labuladong.github.io/algo/images/单调队列/1.png)

这个思路很简单，能理解吧？下面我们开始重头戏，单调队列的实现。

### 二、实现单调队列数据结构

观察滑动窗口的过程就能发现，实现「单调队列」必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显双链表是满足这个条件的。

「单调队列」的核心思路和「单调栈」类似，`push` 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉：

```java
class MonotonicQueue {
// 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
private LinkedList<Integer> maxq = new LinkedList<>();

// 在尾部添加一个元素 n，维护 maxq 的单调性质
public void push(int n) {
    // 将前面小于自己的元素都删除
    while (!maxq.isEmpty() && maxq.getLast() < n) {
        maxq.pollLast();
    }
    maxq.addLast(n);
}
```

你可以想象，加入数字的大小代表人的体重，把前面体重不足的都压扁了，直到遇到更大的量级才停住。

![](https://labuladong.github.io/algo/images/单调队列/3.png)

如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个**单调递减**的顺序，因此我们的 `max` 方法可以可以这样写：

```java
public int max() {
    // 队头的元素肯定是最大的
    return maxq.getFirst();
}
```

`pop` 方法在队头删除元素 `n`，也很好写：

```java
public void pop(int n) {
    if (n == maxq.getFirst()) {
        maxq.pollFirst();
    }
}
```

之所以要判断 `data.getFirst() == n`，是因为我们想删除的队头元素 `n` 可能已经被「压扁」了，可能已经不存在了，所以这时候就不用删除了：

![](https://labuladong.github.io/algo/images/单调队列/2.png)

至此，单调队列设计完毕，看下完整的解题代码：

```java
/* 单调队列的实现 */
class MonotonicQueue {
    LinkedList<Integer> maxq = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!maxq.isEmpty() && maxq.getLast() < n) {
            maxq.pollLast();
        }
        // 然后将 n 加入尾部
        maxq.addLast(n);
    }
    
    public int max() {
        return maxq.getFirst();
    }
    
    public void pop(int n) {
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

/* 解题函数的实现 */
int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List<Integer> res = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先填满窗口的前 k - 1
            window.push(nums[i]);
        } else {
            // 窗口向前滑动，加入新数字
            window.push(nums[i]);
            // 记录当前窗口的最大值
            res.add(window.max());
            // 移出旧数字
            window.pop(nums[i - k + 1]);
        }
    }
    // 需要转成 int[] 数组再返回
    int[] arr = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        arr[i] = res.get(i);
    }
    return arr;
}
```

有一点细节问题不要忽略，在实现 `MonotonicQueue` 时，我们使用了 Java 的 `LinkedList`，因为链表结构支持在头部和尾部快速增删元素；而在解法代码中的 `res` 则使用的 `ArrayList` 结构，因为后续会按照索引取元素，所以数组结构更合适。

关于单调队列 API 的时间复杂度，读者可能有疑惑：`push` 操作中含有 while 循环，时间复杂度应该不是 `O(1)` 呀，那么本算法的时间复杂度应该不是线性时间吧？

这里就用到了 [算法时空复杂度分析使用手册](https://labuladong.github.io/article/fname.html?fname=时间复杂度) 中讲到的摊还分析：

单独看 `push` 操作的复杂度确实不是 `O(1)`，但是算法整体的复杂度依然是 `O(N)` 线性时间。要这样想，`nums` 中的每个元素最多被 `push` 和 `pop` 一次，没有任何多余操作，所以整体的复杂度还是 `O(N)`。空间复杂度就很简单了，就是窗口的大小 `O(k)`。

### 拓展延伸

最后，我提出几个问题请大家思考：

1、本文给出的 `MonotonicQueue` 类只实现了 `max` 方法，你是否能够再额外添加一个 `min` 方法，在 `O(1)` 的时间返回队列中所有元素的最小值？

2、本文给出的 `MonotonicQueue` 类的 `pop` 方法还需要接收一个参数，这显然有悖于标准队列的做法，请你修复这个缺陷。

3、请你实现 `MonotonicQueue` 类的 `size` 方法，返回单调队列中元素的个数（注意，由于每次 `push` 方法都可能从底层的 `q` 列表中删除元素，所以 `q` 中的元素个数并不是单调队列的元素个数）。

也就是说，你是否能够实现单调队列的通用实现：

```java
/* 单调队列的通用实现，可以高效维护最大值和最小值 */
class MonotonicQueue<E extends Comparable<E>> {

    // 标准队列 API，向队尾加入元素
    public void push(E elem);

    // 标准队列 API，从队头弹出元素，符合先进先出的顺序
    public E pop();

    // 标准队列 API，返回队列中的元素个数
    public int size();

    // 单调队列特有 API，O(1) 时间计算队列中元素的最大值
    public E max();

    // 单调队列特有 API，O(1) 时间计算队列中元素的最小值
    public E min();
}
```

我将在 [单调队列通用实现及应用](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_62a692efe4b01a48520b9b9b/1) 中给出单调队列的通用实现和经典习题。更多数据结构设计类题目参见 [数据结构设计经典习题](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_6312b9e5e4b0eca59c2b7e93/1)。



<hr>
<details>
<summary><strong>引用本文的文章</strong></summary>

 - [数据结构设计：最大栈](https://labuladong.github.io/article/fname.html?fname=最大栈)
 - [算法时空复杂度分析实用指南](https://labuladong.github.io/article/fname.html?fname=时间复杂度)

</details><hr>




<hr>
<details>
<summary><strong>引用本文的题目</strong></summary>

<strong>安装 [我的 Chrome 刷题插件](https://mp.weixin.qq.com/s/X-fE9sR4BLi6T9pn7xP4pg) 点开下列题目可直接查看解题思路：</strong>

| LeetCode | 力扣 |
| :----: | :----: |
| [1425. Constrained Subsequence Sum](https://leetcode.com/problems/constrained-subsequence-sum/?show=1) | [1425. 带限制的子序列和](https://leetcode.cn/problems/constrained-subsequence-sum/?show=1) |
| [1696. Jump Game VI](https://leetcode.com/problems/jump-game-vi/?show=1) | [1696. 跳跃游戏 VI](https://leetcode.cn/problems/jump-game-vi/?show=1) |
| [862. Shortest Subarray with Sum at Least K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/?show=1) | [862. 和至少为 K 的最短子数组](https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/?show=1) |
| [918. Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/?show=1) | [918. 环形子数组的最大和](https://leetcode.cn/problems/maximum-sum-circular-subarray/?show=1) |
| - | [剑指 Offer 59 - I. 滑动窗口的最大值](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/?show=1) |

</details>



**＿＿＿＿＿＿＿＿＿＿＿＿＿**

**《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「**进群**」可加入算法群；回复「**全家桶**」可下载配套 PDF 和刷题全家桶**：

![](https://labuladong.github.io/algo/images/souyisou2.png)


======其他语言代码======

[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;

};
```