关于android:使用单调栈解决-下一个更大元素-问题

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

前言

大家好，我是小彭。

明天分享到一种栈的衍生数据结构 —— 枯燥栈（Monotonic Stack）。栈（Stack）是一种满足后进先出（LIFO）逻辑的数据结构，而枯燥栈实际上就是在栈的根底上减少枯燥的性质（枯燥递增或枯燥递加）。那么，枯燥栈是用来解决什么问题的呢？

学习路线图：

1. 枯燥栈的典型问题

枯燥栈是一种特地适宜解决“下一个更大元素”问题的数据结构。

举个例子，给定一个整数数组，要求输入数组中元素 $i$ 前面下一个比它更大的元素，这就是下一个更大元素问题。这个问题也能够形象化地思考：站在墙上向后看，问眼帘范畴内所能看到的下一个更高的墙。例如，站在墙 [3] 上看，下一个更高的墙就是墙 [4]。

形象化思考

这个问题的暴力解法很容易想到：就是遍历元素 $i$ 前面的所有元素，直到找到下一个比 $i$ 更大的元素为止，工夫复杂度是 $O(n)$，空间复杂度是 $O(1)$。单次查问的确没有优化空间了，那屡次查问呢？如果要求输入数组中每个元素的下一个更大元素，那么暴力解法须要的工夫复杂度是 $O(n^2)$。有没有更高效的算法呢？

2. 解题思路

咱们先转变一下思路：

在暴力解法中，咱们每解决一个元素就要去求它的“下一个更大元素”。当初咱们不这么做，咱们每解决一个元素时，因为不分明它的解，所以先将它缓存到某种数据容器中。后续如果能确定它的解，再将其从容器中取出来。 这个思路能够作为“以空间换工夫”优化工夫复杂度的通用思路。

回到这个例子上：

• 在解决元素 [3] 时，因为不分明它的解，只能先将 [3] 放到容器中，持续解决下一个元素；
• 在解决元素 [1] 时，咱们发现它比容器中所有元素都小，只能先将它放到容器中，持续解决下一个元素；
• 在解决元素 [2] 时，咱们察看容器中的 [1] 比以后元素小，阐明以后元素就是 [1] 的解。此时咱们能够把 [1] 弹出，记录后果。再将 [2] 放到容器中，持续解决下一个元素；
• 在解决元素 [1] 时，咱们发现它比容器中所有元素都小，只能先将它放到容器中，持续解决下一个元素；
• 在解决元素 [4] 时，咱们察看容器中的 [3] [2] [1] 都比以后元素小，阐明以后元素就是它们的解。此时咱们能够把它们弹出，记录后果。再将 [4] 放到容器中，持续解决下一个元素；
• 在解决元素 [1] 时，咱们发现它比容器中所有元素都小，只能先将它放到容器中，持续解决下一个元素；
• 遍历完结，所有被弹出过的元素都是有解的，保留在容器中的元素都是无解的。

剖析到这里，咱们发现问题曾经产生转变，问题变成了：“如何寻找在数据容器中小于以后元素的数”。 当初，咱们把注意力集中在这个容器上，思考一下用什么数据结构、用什么算法能够更高效地解决问题。因为这个容器是咱们额定减少的，所以咱们有足够的操作空间。

先说论断：

• 办法 1 – 暴力： 遍历整个数据容器中所有元素，最坏状况（递加序列）下所有数据都进入容器中，单次操作的工夫复杂度是 $O(N)$，整体工夫复杂度是 $O(N^2)$；
• 办法 2 – 二叉堆： 不须要遍历整个容器，只须要比照容器的最小值，直到容器的最小值都大于以后元素。最坏状况（递加序列）下所有数据都进入堆中，单次操作的工夫复杂度是 $O(lgN)$，整体工夫复杂度是 $O(N·lgN)$；
• 办法 3 – 枯燥栈： 咱们发现元素进入数据容器的程序正好是有序的，且后进入容器的元素会先弹出做比照，合乎 “后进先出” 逻辑，所以这个容器数据结构用栈就能够实现。因为每个元素最多只会入栈和出栈一次，所以整体的计算规模还是与数据规模成正比的，整体工夫复杂度是 $O(n)$。

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

3. 优先队列解法

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

咱们能够保护一个小顶堆，每解决一个元素时，先察看堆顶的元素：

• 如果堆顶元素小于以后元素，则阐明曾经确定了堆顶元素的解，咱们将其弹出并记录后果；
• 如果堆顶元素不小于以后元素，则阐明小顶堆内所有元素都是不小于以后元素的，进行察看。

察看完结后，将以后元素退出小顶堆，堆会主动进行堆排序，堆顶就是整个容器的最小值。此时，持续在后续元素上反复这个过程。

题解

fun nextGreaterElements(nums: IntArray): IntArray {
    // 后果数组 
    val result = IntArray(nums.size) {-1}
    // 小顶堆
    val heap = PriorityQueue<Int> { first, second ->
        nums[first] - nums[second]
    }
    // 从前往后查问
    for (index in 0 until nums.size) {
        // while：以后元素比堆顶元素大，阐明找到下一个更大元素
        while (!heap.isEmpty() && nums[index] > nums[heap.peek()]) {result[heap.poll()] = nums[index]
        }
        // 以后元素入堆
        heap.offer(index)
    }
    return result
}

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

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

优先队列解法的工夫复杂度从 $O(N^2)$ 优化到 $O(N·lgN)$，还不错，那还有优化空间吗？

4. 枯燥栈解法

咱们持续剖析发现，元素进入数据容器的程序正好是逆序的，最初退出容器的元素正好就是容器的最小值。此时，咱们不须要用二叉堆来寻找最小值，只须要获取最初一个进入容器的元素就能轻松取得最小值。这合乎 “后进先出” 逻辑，所以这个容器数据结构用栈就能够实现。

这个问题也能够形象化地思考：把数字设想成有 “分量” 的杠铃片，每减少一个杠铃片，会把两头小的杠铃片压扁，以后的大杠铃片就是这些被压扁杠铃片的“下一个更大元素”。

形象化思考

解题模板

// 从前往后遍历
fun nextGreaterElements(nums: IntArray): IntArray {
    // 后果数组 
    val result = IntArray(nums.size) {-1}
    // 枯燥栈
    val stack = ArrayDeque<Int>()
    // 从前往后遍历
    for (index in 0 until nums.size) {
        // while：以后元素比栈顶元素大，阐明找到下一个更大元素
        while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {result[stack.pop()] = nums[index]
        }
        // 以后元素入队
        stack.push(index)
    }
    return result
}

了解了单点栈的解题模板后，咱们来剖析它的复杂度：

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

这道题也能够用从后往前遍历的写法，也是参考资料中提到的解法。 然而，我感觉正向思维更容易了解，也更合乎人脑的思考形式，所以还是比拟举荐小彭的模板（王婆卖瓜）。

解题模板（从后往前遍历）

// 从后往前遍历
fun nextGreaterElement(nums: IntArray): IntArray {
    // 后果数组
    val result = IntArray(nums.size) {-1}
    // 枯燥栈
    val stack = ArrayDeque<Int>()
    // 从后往前查问
    for (index in nums.size - 1 downTo 0) {
        // while：栈顶元素比以后元素小，阐明栈顶元素不再是下一个更大元素，后续不再思考它
        while (!stack.isEmpty() && stack.peek() <= nums[index]) {stack.pop()
        }
        // 输入到后果数组
        result[index] = stack.peek() ?: -1
        // 以后元素入队
        stack.push(nums[index])
    }
    return result
}

5. 典型例题 · 下一个更大元素 I

了解以上概念后，就曾经具备解决枯燥栈常见问题的必要常识了。咱们来看一道 LeetCode 上的典型例题：LeetCode 496.

LeetCode 例题

第一节的示例是求 “在以后数组中寻找下一个更大元素”，而这道题里是求 “数组 1 元素在数组 2 中雷同元素的下一个更大元素”，还是同一个问题吗？其实啊，这是题目抛出的烟雾弹。留神看细节信息：

• 两个没有反复元素的数组 nums1 和 nums2；
• nums1 是 nums2 的子集。

那么，咱们齐全能够先计算出 nums2 中每个元素的下一个更大元素，并把后果记录到一个散列表中，再让 nums1 中的每个元素去散列表查问后果即可。

题解

class Solution {fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
        // 长期记录
        val map = HashMap<Int, Int>()
        // 枯燥栈
        val stack = ArrayDeque<Int>()
        // 从前往后查问
        for (index in 0 until nums2.size) {
            // while：以后元素比栈顶元素大，阐明找到下一个更大元素
            while (!stack.isEmpty() && nums2[index] > stack.peek()) {
                // 输入到长期记录中
                map[stack.pop()] = nums2[index]
            }
            // 以后元素入队
            stack.push(nums2[index])
        }

        return IntArray(nums1.size) {map[nums1[it]] ?: -1
        }
    }
}

6. 典型例题 · 下一个更大元素 II（环形数组）

第一节的示例还有一道变型题，对应于 LeetCode 上的另一道典型题目：503. 下一个更大元素 II

LeetCode 例题

两道题的外围考点都是“下一个更大元素”，区别只在于把“一般数组”变为“环形数组 / 循环数组”，当元素遍历到数组末位后仍然找不到指标元素，则会循环到数组首位持续寻找。这样的话，除了所有数据中最大的元素，其它每个元素都必然存在下一个更大元素。

其实，计算机中并不存在物理上的循环数组，在遇到相似的问题时都能够用假数据长度和取余的思路解决。如果你是前端工程师，那么你应该有印象：咱们在实现有限循环轮播的控件时，有一个小技巧就是给控件 设置一个十分大的数据长度 ，长到永远不可能轮播完结，例如 Integer.MAX_VALUE。每次轮播后索引会加一，但在取数据时会对数据长度取余，这样就实现了循环轮播了。

有限轮播伪代码

class LooperView {private val data = listOf("1", "2", "3")        

    // 假数据长度
    fun getSize() = Integer.MAX_VALUE

    // 应用取余转化为 data 上的下标
    fun getItem(index : Int) = data[index % data.size]
}

回到这道题，咱们的思路也更清晰了。咱们不须要有限查问，所以天然不须要设置 Integer.MAX_VALUE 这么大的假数据，只须要 设置 2 倍的数据长度 ，就能实现循环查问（3 倍、4 倍也能够，但没必要），例如：

题解

class Solution {fun nextGreaterElements(nums: IntArray): IntArray {
        // 后果数组 
        val result = IntArray(nums.size) {-1}
        // 枯燥栈
        val stack = ArrayDeque<Int>()
        // 数组长度
        val size = nums.size
        // 从前往后遍历
        for (index in 0 until nums.size * 2) {
            // while：以后元素比栈顶元素大，阐明找到下一个更大元素
            while (!stack.isEmpty() && nums[index % size] > nums[stack.peek() % size]) {result[stack.pop() % size] = nums[index % size]
            }
            // 以后元素入队
            stack.push(index)
        }
        return result
    }
}

7. 总结

到这里，置信你曾经把握了“下一个更大元素”问题的解题模板了。除了典型例题之外，大部分题目会将“下一个更大元素”的语义暗藏在题目细节中，须要找出题目的形象模型或转变思路能力找到，这是难的中央。

小彭在 20 年的文章里说过枯燥栈是一个绝对冷门的数据结构，包含参考资料和网上的其余材料也广泛持有这个观点。 枯燥栈不能笼罩太大的问题域，利用价值不迭其余数据结构。 —— 2 年前的文章

2 年后从新思考，我不再持有此观点。我当初认为：枯燥栈的要害是“枯燥性”，而栈只是为了配合问题对操作程序的要求而搭配的数据结构。 咱们学习枯燥栈，应该当作学习枯燥性的思维在栈这种数据结构上的利用，而不是学习一种新的数据结构。对此，你怎么看？

下一篇文章，咱们来学习枯燥性的思维在队列上数据结构上的利用 —— 枯燥队列

更多同类型题目：

参考资料

• LeetCode 专题 · 枯燥栈 —— LeetCode 出品
• LeetCode 题解 · 739. 每日温度 —— LeetCode 出品
• 第 9 章 · 枯燥栈 —— liweiwei1419 著
• 枯燥栈解决 Next Greater Number 一类问题 —— labuladong 著