关于android:使用单调队列解决-滑动窗口最大值-问题

本文已收录到  GitHub · AndroidFamily，有 Android 进阶常识体系，欢送 Star。技术和职场问题，请关注公众号 [彭旭锐] 私信我发问。

前言

大家好，我是小彭。

在上一篇文章中，咱们介绍了枯燥栈这种非凡的栈构造，枯燥栈是一种非常适合解决 “下一个更大元素问题” 的数据结构。明天，分享到枯燥栈的孪生兄弟 —— 枯燥队列（Monotonic Queue）。相似地，枯燥队列也是在队列的根底上减少了枯燥的性质（枯燥递增或枯燥递加）。那么枯燥队列是用来解决什么问题的呢？

学习路线图：

1. 枯燥队列的典型问题

枯燥队列是一种用来高效地解决“滑动窗口最大值”问题的数据结构。

举个例子，给定一个整数数组，要求输入数组中大小为 K 的窗口中的最大值，这就是窗口最大值问题。而如果窗口从最左侧逐步滑动到数组的最右端，要求输入每次挪动后的窗口最大值，这就是滑动窗口问题。这个问题同时也是 LeetCode 上的一道典型例题：LeetCode · 239. 滑动窗口最大值

LeetCode 例题

这个问题的暴力解法很容易想到：就是每次挪动后遍历整个滑动窗口找到最大值，单次遍历的工夫复杂度是 $O(k)$，整体的工夫复杂度是 $O(n·k)$，空间复杂度是 $O(1)$。当然，暴力解法里的反复比拟运算也是很显著的，咱们每次仅仅往窗口里减少一个元素，都须要与窗口中所有元素对比找到最大值。

那么，有没有更高效的算法呢？

滑动窗口最大值问题

或者，咱们能够应用一个变量来记录上一个窗口中的最大值，每减少一个新元素，只须要与这个“最大值”比拟即可。

然而，窗口大小是固定的，每退出一个新元素后，也要剔除一个元素。如果剔除的元素正好是变量记录的最大值，那阐明这个值曾经生效。咱们还是须要破费 $O(k)$ 工夫从新找出最大值。那还有更快的办法寻找最大值吗？

2. 解题思路

咱们先用“空间换工夫”的通用思路梳理一下：

在暴力解法中，咱们每挪动一次窗口都须要遍历整个窗口中的所有元素找出“滑动窗口的最大值”。当初咱们不这么做，咱们把滑动窗口中的所有元素缓存到某种数据容器中，每次窗口滑动后也向容器减少一个新的元素，而容器的最大值就天然是滑动窗口的最大值。

当初，咱们的问题曾经产生转变，问题变成了：“如何寻找数据容器中的最大值”。 另外，依据题目条件限度，这个容器是带有束缚的：因为窗口大小是固定的，所以每退出一个新元素后，必然也要剔除一个元素。 咱们的数据容器也要满足这个束缚。 当初，咱们把注意力集中在这个容器上，思考一下用什么数据结构、用什么算法能够更高效地解决问题。因为这个容器是咱们额定减少的，所以咱们有足够的操作空间。

先说论断：

• 办法 1 – 暴力： 遍历整个数据容器中所有元素，单次操作的工夫复杂度是 $O(k)$，整体工夫复杂度是 $O(n·k)$；
• 办法 2 – 二叉堆： 不须要遍历整个数据容器，能够用大顶堆保护容器的最大值，单次操作的工夫复杂度是 $O(lgk)$，整体工夫复杂度是 $O(n·lgk)$；
• 办法 3 – 双端队列： 咱们发现二叉堆中很多两头元素是冗余的，拉低了效率。咱们能够在每解决一个元素时，能够先察看容器中刚刚退出的元素，如果刚刚退出的元素小于以后元素，则间接将其抛弃（后进先出逻辑）。最先退出容器的元素，如果超出了滑动窗口的范畴，也间接将其抛弃（先进先出逻辑）。所以这个容器数据结构要用双端队列实现。因为每个元素最多只会入队和出队一次，所以整体的计算规模还是与数据规模成正比的，整体工夫复杂度是 $O(n)$。

上面，咱们先从优先队列说起。

3. 优先队列解法

寻找最值的问题第一反馈要想到二叉堆。

咱们能够保护一个大顶堆，初始时先把第一个滑动窗口中的前 $k – 1$ 个元素放入大顶堆。滑动窗口每挪动一步，就把一个新的元素放入大顶堆。大顶堆会主动进行堆排序，堆顶的元素就是整个堆中 $k$ 个元素的最值。然而，这个最大值可能是生效的（不在滑动窗口的范畴内），咱们要怎么解决这个束缚呢？

咱们能够用一个小技巧：将元素的下标放入队列中，用 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
    }
}

咱们来剖析优先队列解法的复杂度：

• 工夫复杂度： 最坏状况下（递增序列），所有元素都被增加到优先队列里，优先队列的单次操作工夫复杂度是 $O(lgn)$，所以整体工夫复杂度是 $O(n·lgn)$；
• 空间复杂度： 应用了额定的优先级队列，所以整体的工夫复杂度是 $O(n)$。

优先队列解法的工夫复杂度从 $O(n·k)$ 变成 $O(n·lgn)$，这个成果很难让人称心，有更好的方法吗？

咱们持续剖析发现，因为滑动窗口是从左往右挪动的，所以当一个元素 $nums[i]$ 的前面呈现一个更大的元素 $nums[j]$，那么 $nums[i]$ 就永远不可能是滑动窗口的最大值了，咱们能够永恒地将它剔除掉。然而，在优先队列中，失去价值的 $nums[i]$ 会始终存储在队列中，从而拉低了优先队列的效率。

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
    }
}

枯燥队列与枯燥栈的思路是十分相似的，枯燥栈在每次遍历中，会将栈顶“被压扁的小杠铃片”弹出栈，而枯燥队列在每次遍历中，会将队尾中“被压扁的小杠铃片”弹出队。 枯燥栈在栈顶过滤有效元素，在栈顶获取指标元素，枯燥队列在队尾过滤有效元素，在队头获取指标元素。

了解了枯燥队列的解题模板后，咱们来剖析它的复杂度：

• 工夫复杂度： 尽管代码中有嵌套循环，但它的工夫复杂度并不是 $O(n^2)$，而是 $O(n)$。因为每个元素最多只会入栈和出栈一次，所以整体的计算规模还是与数据规模成正比的，整体工夫复杂度是 $O(n)$；
• 空间复杂度： 最坏状况下（递增序列），所有元素被增加到队列中，所以空间复杂度是 $O(n)$。

5. 枯燥栈、枯燥队列、优先队列比照

5.1 枯燥栈与枯燥队列的抉择

枯燥队列和枯燥栈在很大水平上是相似的，它们均是在原有数据结构的根底上减少的枯燥的性质。那么，什么时候应用枯燥栈，什么时候应用枯燥队列呢？ 次要看你的算法中元素被排除的程序，如果先进入汇合的元素先排除，那么应用栈（LIFO）；如果先进入汇合的元素后排除，那么应用队列（FIFO）。 在例题中，甚至呈现了同时联合栈和队列的状况。

上一篇文章里咱们探讨过枯燥栈，枯燥栈是一种非常适合解决”下一个更大元素“的数据结构。在文章最初我也指出，枯燥栈的要害是“枯燥性”，而不是“栈”。咱们学习枯燥栈和单端队列，应该当作学习枯燥性的思维在栈或者队列上的利用。

咱们曾经不是第一次探讨“枯燥性”了，老读者应该有印象，在探讨二分查找时，咱们已经指出“枯燥性是二分查找的必要条件”。举个例子，对于一个枯燥递增序列，当中位数小于指标数时，那咱们能够确定：左半区间肯定不是解，右半区间可能有解，问题规模间接放大一半。最终整个二分查找算法的工夫复杂度从暴力查找 $O(n)$，升高到 $O(lgn)$。反之，如果数据并不是枯燥的，那么跟中位数比拟就没有意义。

5.2 优先队列与枯燥队列比照

优先队列也叫小顶堆或大顶堆，每从堆顶取一个数据，底层的二叉堆会主动进行堆排序，放弃堆顶元素是整个堆的最值。所以，尽管整个堆不是枯燥的，但堆顶是动静枯燥的。优先队列尽管也叫队列，但它并不能保护元素的地位关系，出队程序和入队程序无关。

6. 总结

到这里，枯燥队列和枯燥栈的内容都讲完了。和枯燥栈一样，除了典型例题之外，大部分题目会将“滑动窗口最大值素”的语义暗藏在题目细节中，须要找出题目的形象模型或转换思路能力找到，这是难的中央。

还是那句话，学习枯燥队列和枯燥栈，应该当作学习枯燥性的思维在这两种数据结构上的利用。你感觉呢？

更多同类型题目：

参考资料

• LeetCode 专题 · 枯燥队列 —— LeetCode 出品
• LeetCode 题解 · 239. 滑动窗口最大值 —— LeetCode 出品
• LeetCode 题解 · 239. 枯燥队列解题详解 —— labuladong 著