摘要：
1，单调队列的介绍
2，单调队列的具体实现
1，单调队列的介绍
单调队列(Monotone queue)是一种单调递增或单调递减的队列，它和我们前面讲的普通队列是一样的，只不过队列中的元素是单调的，如下图所示。
打开网易新闻 查看更多图片
假设有这样一道题，给定一个数组和一个窗口，并且窗口在数组中一直往右滑动，计算滑动过程中窗口内的最大值。
这题解法比较多，假设窗口大小是 m ，滑动次数是 n ：
最直接的方法就是每次滑动之后都要遍历窗口中的所有元素，并找出最大值，这样总的时间复杂度就是O(m*n)。
第二种方法就是使用最大堆，如果堆中元素个数达到 m ，则每次滑动之前先把最早添加到堆中的元素给移除，然后再滑动把后面的元素添加进来，这样总的时间复杂度是O((m+n)log(m+n))，这里的 m+n 实际上就是数组的长度。
第三种方式就是使用稀疏表(Sparse Table)，前面我们刚讲过，它可以用来求区间内的最大值和最小值，但稀疏表主要用来解决静态的RMQ(Range Maximum/Minimum Query区间最值)问题，要频繁的构建ST表，效率很差，时间复杂度是O(n*mlogm)，每次构建的时间复杂度是O(mlogm)，每次滑动都要构建一次，总共需要构建 n 次。
第四种方法就是使用线段树，线段树的功能非常强大，可以进行区间查询，区间求和，求区间的最大值，最小值等。但使用线段树之前需要先构建线段树，线段树构建的时间复杂度是O((m+n)log(m+n))，这里的 m+n 是数组的长度。
第五种方法就是使用单调队列，保证队列中的元素是单调的，这样每次从队列中取值即可，时间复杂度是O(m+n)。