数据结构 | 队列都知道，单调队列有了解吗？

作者: 彭旭锐 | 来源:发表于2021-03-20 17:57 被阅读0次

数据结构 | 队列都知道，单调队列有了解吗？
GCD多线程问题整理
实战PHP数据结构基础之队列
Algorithm小白入门 -- 队列和栈
数据结构 | 栈都知道，单调栈有了解吗？
单调队列与Sliding Window
动态规划之单调队列
数据结构（三）-- 优先队列
阻塞队列 part1
iOS 的串行队列和并发队列中的任务是如何执行的

点赞关注，不再迷路，你的支持对我意义重大！

🔥 Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）

历史上的今天

2013 年 3 月 20 日，Docker 发布。
Docker 是一套平台即服务（PaaS）产品，使用操作系统级的虚拟化技术，以称为 “容器” 的包来交付软件，而容器之间相互隔离，可大大提高软件交付速度。Docker 轻量和可移植的特性尤其适用于动态和分布式环境，它的兴起为软件开发带来了一场革命。—— 《了不起的程序员》

前言

上一篇文章我们讨论了单调栈，单调栈是一种非常适合处理 下一个更大元素（Next Greater Number ） 问题的数据结构，今天我们来讨论它的孪生兄弟 —— 单调队列；
单调队列是一种非常适合处理 滑动窗口最大值 问题的数据结构，在面试中比较冷门，建议应试者合理安排学习时间；
在这篇文章里，我将梳理单调队列的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

1. 单调队列基础

单调队列和单调栈在很大程度上是类似的，它们均是在原有数据结构的基础上增加的单调的性质。 至于单调性的作用，在上一篇文章里我们已经讨论过了，就不重复展开了。记住关键结论是：利用单调的特性，以空间换时间优化时间复杂度。

那么，什么时候使用单调栈，什么时候使用单调队列呢？主要看你的算法中元素被排除的顺序，如果先进入集合的元素先排除，那么使用栈（LIFO）；如果先进入集合的元素后排除，那么使用队列（FIFO）。

2. 单调队列解题框架

239. 滑动窗口最大值 【题解】

这一节我们来看单调队列的原始题目，并根据这个例子来讨论单调栈的解题框架。

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

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

2.1 暴力解法

这道题的暴力解法很容易想到：每次移动窗口，遍历窗口元素找出最大值，整体的时间复杂度是 $O(nk)$ ，空间复杂度是 $O(1)$ 。这个过程中存在很多重复的比较操作：我们每次仅仅往窗口里增加一个元素，剩下的其他元素也要相互比较来找出最值。

那么，有没有办法用 $O(1)$ 时间复杂度找到窗口移动后的最大值呢？我们可以使用一个变量来记录最大值，此时只需要拿新加入的元素与这个 “最大值” 比较。但是，别忘了每加入一个元素必然还需要剔除一个元素，如果剔除的元素刚好是 “最大值”，那么你还是需要 $O(k)$ 时间去找到那个 “次大值”。

既然一个变量搞不定，那么就多加几个变量，直接把滑动窗口内的最大值、次大值、次次大值 .....、最小值都 「记忆化」，我就不信 $O(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()
        }
    }
}

复杂度分析：