我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第1篇文章，点击查看活动详情

引入

阅读本文，你将会收获：

1. 什么是单调队列
2. 单调队列能解决的问题
3. 单调队列经典题目的解法

首先，栈与队列想必各位都已经是很熟悉不过的数据结构了。

• 栈：一种先入后出【FILO】的数据结构
• 队列：一种先进先出【FIFO】的数据结构

那么，所谓的单调栈和单调队列又是什么意思呢？从字面意思上来看，所谓的“单调”就是指单调递增或者单调递减，没错，正如字面意思一般，单调栈及单调队列就是指的是栈/队列内元素单调递增或单调递减。

疑问？

不知道各位是否有这种疑问，如果是这样的定义的话，在JavaScript中，我要实现这样的功能，我把所有的元素先全部塞入数组中，然后再进行排序，就可以按照栈或者队列的方式进行出栈和出队了，如下：

class MonoQueue {
    constructor() {
        this.data = [];
    }
    
    enQueue(v) {
        this.data.push(v);
        this.data.sort();
    }
    
    deQueue() {
        this.data.shift();
    }
}

但是单调队列的意义并不在于此，单调队列并不需要将所有的元素全部保存起来，我只需要保证我的队列中的元素是单调的即可，这言外之意呢就是：如果有会造成队列不单调的元素进入，我会丢弃掉一些元素来保证队列的单调性！

对于单调队列来说，同样也是如此。为了保证整个栈的单调性，我可以选择性的丢弃一些元素。接下来就详细的介绍一下单调栈与单调队列。

什么是单调队列

单调队列

在某乎上看到一个对单调队列很形象的比喻，此处引用一下：

“如果一个选手比你小还比你强，你就可以退役了。” ——单调递减队列的原理

单调队列是一个双端队列，这意味着该队列既可以像栈一样先入后出，也可以像队列一样先入先出。

对于单调递减队列来说，其入队规则如下：

即将入队的元素与队尾的元素进行比较（新来的），如果其值比你大(比你还强)，就从队尾弹出这个元素（退役），再与队尾的元素进行比较，直到遇到比它大的值为止。

下面通过一个例子来进行说明：

假设现在需要在大学中选拔出一个最强的人来作为代表参加ACM竞赛，下列数组中的数字表示一个人的编程能力，数字越大则能力越强。红色的框则表示大学四年时间。

按照上面我们讲过的规则：

1. 我们的优先队列先入队2，此时队列为空，所以2顺利的进入了队列，此时队列中的元素有： [2]。
2. 然后准备将1入队，首先与队尾的元素比较，1比2小，所以1顺利的进入了队列，队列中的元素有：[2, 1] 此时队列依然是单调递减
3. 准备将7入队，首先与队尾的元素进行比较，发现7比1大，那么将1从队尾出队！此时队列中只剩余[2]，再继续向前比较，发现7依然比2大，所以2从队尾出队，此时队列为空了，将7入队，此时队列中的元素为：[7]
4. 准备将4入队，4比7小，此时队列中的的元素为 [7, 4]

对于前4个元素，其中最大的元素就是单调队列中队头的元素！也就是说，这一届的学生中，大二的这位同学最强！

随着时间流逝，老学长离开，新生加入校园，又开始了新的一轮选拔。

有一名能力为3的新生参加了竞选，我们将其入队，发现比7小，所以现在队列中的元素有：[7, 4, 3]，所以，第二届中，依然还是上一届大二，这届大三的同学最强。

让我们继续，时间不断流逝。。。

此时，一位能力为6的同学加入了，准备将其加入单调队列中，发现它比4和3都要大，所以4和3从队尾出队。6加入其中，此时队列中的元素有：[7, 6]。

看来这位第一届大二的同学恐怖如斯。

好了，以上就是关于单调队列的理论知识，接下来我们来看下如何运用。

此处引用LeetCode 239.滑动窗口的最大值为例子：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置	最大值
[1 3 -1] -3 5 3 6 7	3
1 [3 -1 -3] 5 3 6 7	3
1 3 [-1 -3 5] 3 6 7	5
1 3 -1 [-3 5 3] 6 7	5
1 3 -1 -3 [5 3 6] 7	6
1 3 -1 -3 5 [3 6 7]	7

这道题可以使用单调队列完美的求解。首先，给出单调队列的代码：

class MonoQueue {
    constructor() {
        this.q = [];
    }

    last() {
        return this.q[this.q.length - 1];
    }

    push(val) {
        while (this.q.length !== 0 && val > this.last()) {
            this.q.pop();
        }
        this.q.push(val);
    }

    pop(val) {
        if (this.q.length !== 0 && val === this.q[0]) {
            this.q.shift();
        }
    }

    front() {
        return this.q[0];
    }
}

最后，我们只需要不断的移动滑动窗口即可了，最后读取单调队列中队头的值即可。

var maxSlidingWindow = function(nums, k) {
    const q = new MonoQueue();
    const result = [];
    for (let i = 0; i < k; i++) {
        q.push(nums[i]);
    }
    result.push(q.front());
    for (let i = k; i < nums.length; i++) {
        q.pop(nums[i - k]);
        q.push(nums[i]);
        result.push(q.front());
    }

    return result;
};

小结

小小总结一下，单调队列是一种主要用于解决滑动窗口类问题的数据结构，即，在长度为 n 的序列中，求每个长度为 m 的区间的区间最值。

---

【预告】

文章的下篇将介绍单调栈的概念及其应用，敬请期待，如果你觉得本文对你有用，请别忘了给作者点赞~