点赞关注，不再迷路，你的支持对我意义重大！
🔥 Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见 已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）
历史上的今天
2013 年 3 月 20 日，Docker 发布。
Docker 是一套平台即服务（PaaS）产品，使用操作系统级的虚拟化技术，以称为 “容器” 的包来交付软件，而容器之间相互隔离，可大大提高软件交付速度。Docker 轻量和可移植的特性尤其适用于动态和分布式环境，它的兴起为软件开发带来了一场革命。—— 《了不起的程序员》
前言
- 上一篇文章 我们讨论了单调栈，单调栈是一种非常适合处理 下一个更大元素（Next Greater Number ） 问题的数据结构，今天我们来讨论它的孪生兄弟 —— 单调队列；
- 单调队列是一种非常适合处理 滑动窗口最大值 问题的数据结构，在面试中比较冷门，建议应试者合理安排学习时间；
- 在这篇文章里，我将梳理单调队列的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
目录
1. 单调队列基础
单调队列和单调栈在很大程度上是类似的，它们均是在原有数据结构的基础上增加的单调的性质。 至于单调性的作用，在 上一篇文章 里我们已经讨论过了，就不重复展开了。记住关键结论是：利用单调的特性，以空间换时间优化时间复杂度。
那么，什么时候使用单调栈，什么时候使用单调队列呢？主要看你的算法中元素被排除的顺序，如果先进入集合的元素先排除，那么使用栈（LIFO）；如果先进入集合的元素后排除，那么使用队列（FIFO）。
2. 单调队列解题框架
239. 滑动窗口最大值 【题解】
这一节我们来看单调队列的原始题目，并根据这个例子来讨论单调栈的解题框架。
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
2.1 暴力解法
这道题的暴力解法很容易想到：每次移动窗口，遍历窗口元素找出最大值，整体的时间复杂度是，空间复杂度是
。这个过程中存在很多重复的比较操作：我们每次仅仅往窗口里增加一个元素，剩下的其他元素也要相互比较来找出最值。
那么，有没有办法用时间复杂度找到窗口移动后的最大值呢？我们可以使用一个变量来记录最大值，此时只需要拿新加入的元素与这个 “最大值” 比较。但是，别忘了每加入一个元素必然还需要剔除一个元素，如果剔除的元素刚好是 “最大值”，那么你还是需要
时间去找到那个 “次大值”。
既然一个变量搞不定，那么就多加几个变量，直接把滑动窗口内的 最大值、次大值、次次大值 .....、最小值都 「记忆化」，我就不信 搞不定了，空间换时间的事嘛！
2.2 单调队列解法
下面，我们来讨论单调队列的解法，数据结构基础是双端队列：
- 1、从左到右遍历每个元素，维护一个单调递增队列（从队尾到队头单调递增）；
- 2、当队列为空，将当前元素入队；
- 3.1 当队列不为空，如果当前元素大于等于队尾元素，那么循环弹出队尾元素，直到队列为空或者当前元素小于队尾元素；
- 3.2 当队列不为空，如果当前元素小于队尾元素，说明当前元素小于队列内所有元素（单调性），将当前元素入队。
- 4、窗口移动时，如果剔除的元素正好是队头元素，那么将该元素出队；如果不是，那说明它已经在 第 3.1 步 中被提前排除了；
- 5、获取队列的最大值，只需要查看队头元素即可。
—— 图片引用自 https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/ labuladong 著
class Solution {
fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
val result = IntArray(nums.size - k + 1)
1、维护一个从队尾到队头单调递增的队列
val queue = LinkedList<Int>()
for ((index, num) in nums.withIndex()) {
if (index < k - 1) {
2、先填满窗口前 k - 1
queue.offerMonotonic(num)
} else {
3、下一个元素入队，此时窗口大小为 k
queue.offerMonotonic(num)
4、记录最大值
result[index - k + 1] = queue.max()
5、窗口左侧元素出队
queue.poll(nums[index - k + 1])
}
}
return result
}
// -----------------------------------------------------
// 单调队列：基于双端队列，从队尾到队头单调递增
// -----------------------------------------------------
private fun <T : Comparable<T>> Deque<T>.offerMonotonic(t: T) {
while (isNotEmpty() && peekLast() < t) {
pollLast()
}
offer(t)
}
private fun <T> Deque<T>.max(): T {
return peekFirst()!!
}
private fun <T> Deque<T>.poll(t: T) {
if (isNotEmpty() && peekFirst() == t) {
pollFirst()
}
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
虽然代码中有两层循环，但是算法的时间复杂度并不是，这是因为内层循环并不是搜索窗口（在暴力解法中，内层循环才是搜索整个窗口）。事实上，对于每个元素，它最多会入队和出队一次，不会因为数据规模增大而导致每个元素增加额外的操作，所以每次操作的时间复杂度是
。
3. 总结
- 单调栈是在双端队列的基础上，利用了单调的特性，以空间换时间优化时间复杂度；
- 当遇到滑动窗口的最大值问题时，可以考虑使用单调队列处理；
- 与单调栈类似，单调队列也不能覆盖太大的问题域，应用价值不及其他数据结构。
- 最后，你可以思考下这个问题能否用单调栈解决？如果不行，为什么？
参考资料
- 《滑动窗口的最大值 · 官方题解》 —— LeetCode
- 《单调队列》 —— labuladong 著
创作不易，你的「三连」是丑丑最大的动力，我们下次见！
网友评论