前言
大家好，我是小彭。
在上一篇文章中，我们介绍了单调栈这种特殊的栈结构，单调栈是一种非常适合处理 “下一个更大元素问题” 的数据结构。今天，分享到单调栈的孪生兄弟 —— 单调队列（Monotonic Queue）。类似地，单调队列也是在队列的基础上增加了单调的性质（单调递增或单调递减）。那么单调队列是用来解决什么问题的呢？
学习路线图：
1. 单调队列的典型问题
单调队列是一种用来高效地解决 “滑动窗口最大值” 问题的数据结构。
举个例子，给定一个整数数组，要求输出数组中大小为 K 的窗口中的最大值，这就是窗口最大值问题。而如果窗口从最左侧逐渐滑动到数组的最右端，要求输出每次移动后的窗口最大值，这就是滑动窗口问题。这个问题同时也是 LeetCode 上的一道典型例题：LeetCode · 239. 滑动窗口最大值
LeetCode 例题
那么，有没有更高效的算法呢？
滑动窗口最大值问题
或许，我们可以使用一个变量来记录上一个窗口中的最大值，每增加一个新元素，只需要与这个 “最大值” 比较即可。
2. 解题思路
我们先用 “空间换时间” 的通用思路梳理一下：
在暴力解法中，我们每移动一次窗口都需要遍历整个窗口中的所有元素找出 “滑动窗口的最大值”。现在我们不这么做，我们把滑动窗口中的所有元素缓存到某种数据容器中，每次窗口滑动后也向容器增加一个新的元素，而容器的最大值就自然是滑动窗口的最大值。
现在，我们的问题已经发生转变，问题变成了：“如何寻找数据容器中的最大值”。 另外，根据题目条件限制，这个容器是带有约束的：因为窗口大小是固定的，所以每加入一个新元素后，必然也要剔除一个元素。 我们的数据容器也要满足这个约束。 现在，我们把注意力集中在这个容器上，思考一下用什么数据结构、用什么算法可以更高效地解决问题。由于这个容器是我们额外增加的，所以我们有足够的操作空间。
先说结论：
下面，我们先从优先队列说起。
3. 优先队列解法
寻找最值的问题第一反应要想到二叉堆。
我们可以用一个小技巧：将元素的下标放入队列中，用 nums[index] 比较元素大小，用 index 判断元素有效性。 此时，每次取堆顶元素时，如果发现该元素的下标超出了窗口范围，就直接丢弃。
题解
class Solution {
fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
// 结果数组
val result = IntArray(nums.size - k + 1) {-1}
// 大顶堆
val heap = PriorityQueue<Int> { first, second ->
nums[second] - nums[first]
}
for (index in nums.indices) {
if (index < k - 1) {
heap.offer(index)
continue
}
heap.offer(index)
// while：丢弃堆顶超出滑动窗口范围的失效元素
while (!heap.isEmpty() && heap.peek() < index - k + 1) {
// 丢弃
heap.poll()
}
// 堆顶元素就是最大值
result[index - k + 1] = nums[heap.peek()]
}
return result
}
}
我们来分析优先队列解法的复杂度：
4. 单调队列解法
我们可以维护一个数据容器，第一个元素先放到容器中，后续每处理一个元素，先观察容器中刚刚加入的元素，如果刚刚加入的元素小于当前元素，则直接将其丢弃（因为新增加的元素排在后面，会更晚地离开滑动窗口，所以中间的小元素永远没有资格了），避免拉低效率。
继续分析我们还发现：
- 这个数据容器中后进入的元素需要先弹出与当前元素对比，符合 “后进先出” 逻辑，所以这个数据结构要用栈；
- 这个数据容器中先进入的元素需要先弹出丢弃（离开滑动窗口），符合 “先进先出” 逻辑，所以这个数据结构要用队列；
因此，这个数据结构同时具备栈和队列的特点，是需要同时在两端操作的双端队列。这个问题也可以形象化地思考：把数字想象为有 “重量” 的的杠铃片，滑动窗口每移动一次后，新增加的大杠铃片会把中间小的杠铃片压扁，后续不再考虑它们。
形象化思考
题解
class Solution {
fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
// 结果数组
val result = IntArray(nums.size - k + 1) { -1 }
// 单调队列（基于双端队列）
val queue = LinkedList<Int>()
for (index in nums.indices) {
// while：队尾元素比当前元素小，说明队尾元素不再可能是最大值，后续不再考虑它
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[index]) {
// 抛弃队尾元素
queue.pollLast()
}
queue.offerLast(index)
if (index < k - 1) {
continue
}
// if：移除队头超出滑动窗口范围的元素
if (!queue.isEmpty() && queue.peekFirst() < index - k + 1) {
queue.pollFirst()
}
// 从队头取目标元素
result[index - k + 1] = nums[queue.peekFirst()]
}
return result
}
}
单调队列与单调栈的思路是非常类似的，单调栈在每次遍历中，会将栈顶 “被压扁的小杠铃片” 弹出栈，而单调队列在每次遍历中，会将队尾中 “被压扁的小杠铃片” 弹出队。 单调栈在栈顶过滤无效元素，在栈顶获取目标元素，单调队列在队尾过滤无效元素，在队头获取目标元素。
理解了单调队列的解题模板后，我们来分析它的复杂度：
5. 单调栈、单调队列、优先队列对比
5.1 单调栈与单调队列的选择
单调队列和单调栈在很大程度上是类似的，它们均是在原有数据结构的基础上增加的单调的性质。那么，什么时候使用单调栈，什么时候使用单调队列呢？ 主要看你的算法中元素被排除的顺序，如果先进入集合的元素先排除，那么使用栈（LIFO）；如果先进入集合的元素后排除，那么使用队列（FIFO）。 在例题中，甚至出现了同时结合栈和队列的情况。
上一篇文章里我们讨论过单调栈，单调栈是一种非常适合解决 ”下一个更大元素“ 的数据结构。在文章最后我也指出，单调栈的关键是 “单调性”，而不是 “栈”。我们学习单调栈和单端队列，应该当作学习单调性的思想在栈或者队列上的应用。
5.2 优先队列与单调队列对比
优先队列也叫小顶堆或大顶堆，每从堆顶取一个数据，底层的二叉堆会自动进行堆排序，保持堆顶元素是整个堆的最值。所以，虽然整个堆不是单调的，但堆顶是动态单调的。优先队列虽然也叫队列，但它并不能维护元素的位置关系，出队顺序和入队顺序无关。
| 数据结构 | 特点 | 单调性 / 有序性 |
|---|---|---|
| 单调栈 | 后进先出（LIFO），出队顺序由入栈顺序决定 | 静态 |
| 单调队列 | 先进先出（FIFO），出队顺序由入队顺序决定 | 静态单调序列 |
| 优先队列 | 出队顺序与入队顺序无关，而由优先级顺序决定 | 整个堆不是单调的，但堆顶是动态单调的 |
6. 总结
到这里，单调队列和单调栈的内容都讲完了。和单调栈一样，除了典型例题之外，大部分题目会将 “滑动窗口最大值素” 的语义隐藏在题目细节中，需要找出题目的抽象模型或转换思路才能找到，这是难的地方。
还是那句话，学习单调队列和单调栈，应该当作学习单调性的思想在这两种数据结构上的应用。你觉得呢？
更多同类型题目：
| 单调队列 | 难度 | 题解 |
|---|---|---|
| 239. 滑动窗口最大值 | Hard | 【题解】 |
| 918. 环形子数组的最大和 | Medium | 【题解】 |
| 面试题59 - II. 队列的最大值 | Medium | 【题解】 |
参考资料
- LeetCode 专题 · 单调队列 —— LeetCode 出品
- LeetCode 题解 · 239. 滑动窗口最大值 —— LeetCode 出品
- LeetCode 题解 · 239. 单调队列解题详解 —— labuladong 著
网友评论