所谓单调队列——即元素具有单调性且同时保持着队列性质的数据结构。这个数据结构使用频率不是很高，笔者在之前也没有接触过，但是很多时候可以简化问题，对一些算法优化也大有裨益。
背景
记录这篇文章的背景，要从周末时候刷到的leetcode 上239上的问题开始谈起了。题目的名称叫Sliding Window Maximum。以下是这个问题的描述。
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums=[1,3,-1,-3,5,3,6,7], and k= 3.
Window position Max
--------------- -----
[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
Therefore, return the max sliding window as[3,3,5,5,6,7].
我们分析下这个题目，滑动窗口每移动一次都要将原窗口中的元素弹出一个，压入一个，同时获取一个最大值。到这一步，我们能联想到什么样的数据结构呢？双向队列+优先级队列。如果我们使用一个优先级队列来做这个题目，毫无疑问是可以完成的。笔者一开始也是想使用优先级队列作为解题的方法。
但是一来对一个堆执行查找和随机删除并不是件很愉快的事情、二来每次执行heapify操作的时间复杂度为O(logk)，总的时间代价需要O(nlogk)，要知道，题目提示这个题目只需要线性时间内就可以解决。
那么问题来了，结合我们一开始的分析，如果我们需要在线性时间内解决这个问题，则我们的压入，弹出，获取最大这三件事都需要O(1)内完成。【这真的可能做到吗？存在这么厉害的数据结构嘛？】
单调队列
答案是能做到的。讨论区一个叫fentoyal的大神（600+的reputation）指出，这是一道典型的单调队列的问题。原文请戳这里
Sliding window minimum/maximum = monotonic queue. I smelled the solution just when I read the title.
这位大牛提供了一份可以直接拿来使用的MonotonicQueue的代码，供我们直接使用。我们来看看这份代码。
Monoqueue
单调队列的操作包括：
push：在队尾压入元素O(1)【这里的O(1)是由于所有的元素都入队一次，出队一次均摊意义上的O(1)】
pop：弹出队首的元素（最大元素）【O(1)】
max：返回队首的最大元素【O(1)】
这份代码使用双向队列deque作为容器存放元素。元素的类型设置为了pair——为每一个元素添加了一个计数器，记录的当前元素和上一个比它大的元素之间的元素个数（下文中我们称为count）。有点拗口（表达能力还需要训练...）。其实简单地说，就是记录在弹出这个元素之前还需要弹出多少个元素，我们不记录这些元素到底是什么（因为他们是什么并不重要，相反是一种浪费），而是记录这样的元素到底有多少个。
举个例子：对于一个队列a[i](ki)，a[i+1](ki+1) 【括号中的数字表示count】a[i] >= a[i+1]
其中ki+1表示在a[i] 和a[i+1]中间有多少个元素。我们不关注这些元素，只关注这样的元素有多少个。如此想想，其实我们deque中保存的仅仅是有可能作为max被弹出的元素，因此我们的push操作的速度要比我们想象中快得多。【本身就是均摊意义上的O(1)】
笔者觉得这份实现较为优雅。拿来和大家分享下~侵删。
单调队列的应用
有了这个单调队列，我们可以直接使用它来解决我们这道Sliding Window
代码如下：
accept
我们利用单调队列，讲一个O(nlogn)的问题简化为了O(n).
所以当我们在优化DP问题，维护队列状态（最大最小）的时候，不妨尝试下单调队列
参考文献：
网友评论