前言

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

目录

1. 单调队列基础

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

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

2. 单调队列解题框架

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

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

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

2.1 暴力解法

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

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

既然一个变量搞不定，那么就多加几个变量，直接把滑动窗口内的 最大值、次大值、次次大值 .....、最小值都 「记忆化」，我就不信 O(1)O(1)O(1) 搞不定了，空间换时间的事嘛！

2.2 单调队列解法

下面，我们来讨论单调队列的解法，数据结构基础是双端队列：

• 1、从左到右遍历每个元素，维护一个单调递增队列（从队尾到队头单调递增）；
• 2、当队列为空，将当前元素入队；
• 3.1 当队列不为空，如果当前元素大于等于队尾元素，那么循环弹出队尾元素，直到队列为空或者当前元素小于队尾元素；
• 3.2 当队列不为空，如果当前元素小于队尾元素，说明当前元素小于队列内所有元素（单调性），将当前元素入队。
• 4、窗口移动时，如果剔除的元素正好是队头元素，那么将该元素出队；如果不是，那说明它已经在 第 3.1 步 中被提前排除了；
• 5、获取队列的最大值，只需要查看队头元素即可。

—— 图片引用自 leetcode-cn.com/problems/sl… 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()
        }
    }
}
复制代码

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(k)

虽然代码中有两层循环，但是算法的时间复杂度并不是O(nk)O(nk)O(nk)，这是因为内层循环并不是搜索窗口（在暴力解法中，内层循环才是搜索整个窗口）。事实上，对于每个元素，它最多会入队和出队一次，不会因为数据规模增大而导致每个元素增加额外的操作，所以每次操作的时间复杂度是O(1)O(1)O(1)。

3. 总结

• 单调栈是在双端队列的基础上，利用了单调的特性，以空间换时间优化时间复杂度；
• 当遇到滑动窗口的最大值问题时，可以考虑使用单调队列处理；
• 与单调栈类似，单调队列也不能覆盖太大的问题域，应用价值不及其他数据结构；
• 最后，你可以思考下这个问题能否用单调栈解决？如果不行，为什么？