本文已收录到 AndroidFamily，技术和职场问题，请重视大众号 [彭旭锐] 提问。

前语

大家好，我是小彭。

今日共享到一种栈的衍生数据结构 —— 单调栈（Monotonic Stack）。栈（Stack）是一种满足后进先出（LIFO）逻辑的数据结构，而单调栈实际上便是在栈的基础上增加单调的性质（单调递加或单调递减）。那么，单调栈是用来处理什么问题的呢？

思维导图：

1. 单调栈的典型问题

单调栈是一种特别合适处理 “下一个更大元素” 问题的数据结构。

举个例子，给定一个整数数组，要求输出数组中元素 ii 后边下一个比它更大的元素，这便是下一个更大元素问题。这个问题也能够形象化地考虑：站在墙上向后看，问视野范围内所能看到的下一个更高的墙。例如，站在墙 [3] 上看，下一个更高的墙便是墙 [4] 。

形象化考虑

这个问题的暴力解法很简单想到：便是遍历元素 ii 后边的一切元素，直到找到下一个比 ii 更大的元素中止，时刻复杂度是 O(n)O(n)，空间复杂度是 O(1)O(1)。单次查询确实没有优化空间了，那多次查询呢？假如要求输出数组中每个元素的下一个更大元素，那么暴力解法需要的时刻复杂度是 O(n2)O(n^2) 。有没有更高效的算法呢？

2. 解题思路

咱们先改变一下思路：

在暴力解法中，咱们每处理一个元素就要去求它的 “下一个更大元素”。现在咱们不这么做，咱们每处理一个元素时，由于不清楚它的解，所以先将它缓存到某种数据容器中。后续假如能确认它的解，再将其从容器中取出来。 这个思路能够作为 “以空间换时刻” 优化时刻复杂度的通用思路。

回到这个例子上：

  • 在处理元素 [3] 时，由于不清楚它的解，只能先将 [3] 放到容器中，持续处理下一个元素；

  • 在处理元素 [1] 时，咱们发现它比容器中一切元素都小，只能先将它放到容器中，持续处理下一个元素；

  • 在处理元素 [2] 时，咱们调查容器中的 [1] 比当时元素小，阐明当时元素便是 [1] 的解。此刻咱们能够把 [1] 弹出，记载成果。再将 [2] 放到容器中，持续处理下一个元素；

  • 在处理元素 [1] 时，咱们发现它比容器中一切元素都小，只能先将它放到容器中，持续处理下一个元素；

  • 在处理元素 [4] 时，咱们调查容器中的 [3] [2] [1] 都比当时元素小，阐明当时元素便是它们的解。此刻咱们能够把它们弹出，记载成果。再将 [4] 放到容器中，持续处理下一个元素；

  • 在处理元素 [1] 时，咱们发现它比容器中一切元素都小，只能先将它放到容器中，持续处理下一个元素；

  • 遍历完毕，一切被弹出过的元素都是有解的，保留在容器中的元素都是无解的。

剖析到这儿，咱们发现问题现已产生改变，问题变成了：“如何寻觅在数据容器中小于当时元素的数”。 现在，咱们把留意力集中在这个容器上，考虑一下用什么数据结构、用什么算法能够更高效地处理问题。由于这个容器是咱们额定增加的，所以咱们有满足的操作空间。

先说定论：

  • 办法 1 – 暴力： 遍历整个数据容器中一切元素，最坏状况（递减序列）下一切数据都进入容器中，单次操作的时刻复杂度是 O(N)O(N)，全体时刻复杂度是 O(N2)O(N^2)；
  • 办法 2 – 二叉堆： 不需要遍历整个容器，只需要比照容器的最小值，直到容器的最小值都大于当时元素。最坏状况（递减序列）下一切数据都进入堆中，单次操作的时刻复杂度是 O(lgN)O(lgN)，全体时刻复杂度是 O(N⋅lgN)O(N·lgN)；
  • 办法 3 – 单调栈： 咱们发现元素进入数据容器的次序正好是有序的，且后进入容器的元素会先弹出做比照，契合 “后进先出” 逻辑，所以这个容器数据结构用栈就能够完成。由于每个元素最多只会入栈和出栈一次，所以全体的核算规划仍是与数据规划成正比的，全体时刻复杂度是 O(n)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(lgN)，所以全体时刻复杂度是 O(N⋅lgN)O(N·lgN)；
  • 空间复杂度： 使用了额定的优先行列，所以全体的空间复杂度是 O(N)O(N)。

优先行列解法的时刻复杂度从 O(N2)O(N^2) 优化到 O(N⋅lgN)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(N2)O(N^2)，而是 O(N)O(N)。由于每个元素最多只会入栈和出栈一次，所以全体的核算规划仍是与数据规划成正比的，全体时刻复杂度是 O(N)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 年后从头考虑，我不再持有此观点。我现在认为：单调栈的关键是 “单调性”，而栈只是为了配合问题对操作次序的要求而搭配的数据结构。 咱们学习单调栈，应该当作学习单调性的思想在栈这种数据结构上的使用，而不是学习一种新的数据结构。对此，你怎么看？

下一篇文章，咱们来学习单调性的思想在行列上数据结构上的使用 —— 单调行列

更多同类型标题：

单调栈 难度 题解
496. 下一个更大元素 I Easy 【题解】
1475. 商品扣头后的终究价格 Easy 【题解】
503. 下一个更大元素 II Medium 【题解】
739. 每日温度 Medium 【题解】
901. 股票价格跨度 Medium 【题解】
1019. 链表中的下一个更大节点 Medium 【题解】
402. 移掉 K 位数字 Medium 【题解】
42. 接雨水 Hard 【题解】
84. 柱状图中最大的矩形 Hard 【题解】

版权声明

本文为稀土技术社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！

参考资料

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