前言

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

目录

1. 单调栈基础

1.1 定义

栈（Stack）是一种满足后进先出（LIFO）逻辑的数据结构，大家都很熟悉了，单调栈实际上就是在栈的基础上增加单调的性质。

比如有序就是最耳熟能详的单调性，每次新元素入栈时，我们可以采用一些额外的逻辑保证栈内元素都是有序的，这样我们就得到了一个单调栈。出栈的时候不需要增加额外的逻辑，因为对于一个单调栈（或者下篇文章提到的单调队列），移除首尾的元素后剩下的元素肯定还是满足单调性的。

单调性

单调性（monotonicity）也可以叫做增减性，可以定性地描述两个变量之间的关系。当变量xxx在其定义区间内增大时，函数y=f(x)y= f(x)y=f(x)随着增大（或减小），则称函数 y 在该区间单调递增（或单调递减）。

1.2 作用

理解了单调栈的定义，下一个问题就是单调栈有什么用？

老读者应该有印象，我们不是第一次讨论单调性了。我们在 《算法 | 下次面试遇到二分查找，别再写错了》 就已经提过单调性。还记得吗，我们说单调性是二分查找的必要条件。

为什么单调性是二分查找必要条件呢？因为在二分查找里，我们需要对比目标数与数组的中位数，来确定目标数是落在左半区间，还是右半区间。举个例子，对于一个单调递增序列，当中位数小于目标数时，那我们可以确定：左半区间一定不是解，右半区间可能有解。

此时，问题规模减少了一半（减治），整个二分查找算法的时间复杂度从暴力查找 O(n)O(n)O(n)，降低到O(lgn)O(lgn)O(lgn)，这里面单调性功不可没。

回到主题，单调栈里的单调性有什么用？栈里虽然没有中位数的概念，但是有栈顶的概念。我们可以利用栈顶来判断栈内其他元素是否存在解。 举个例子，对于一个从栈底到栈顶单调递增的栈，当栈顶元素小于目标数，那么我们可以确定：栈内元素都是小于目标数的；而当栈顶元素大于目标数，那么只有栈顶前面一部分元素大于目标数。

小结：利用单调的特性，以空间换时间优化时间复杂度。

1.3 局限性

相比于其他数据结构，单调栈并不能覆盖太大的问题域，所以这种数据结构的应用价值就打折扣了。也只有 下一个更大元素（Next Greater Number ） 这一类问题，精准命中单调栈的射程范围。在 第 3 节 中，我整理了大量典型例题，应该能覆盖常见的题型，多去看看加深理解。

2. 单调栈解题框架

前面的内容相信大家很快就能理解了，我们直接看单调栈的原始题目 739. 每日温度（Medium），并根据这个例子来讨论单调栈的解题框架。

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
复制代码

这个问题的暴力解法很容易想到：对每个元素扫描后续的每个元素，找到第一个更大的元素，整体时间复杂度是O(n2)O(n^2)O(n2)，空间复杂度是O(1)O(1)O(1)。

下面我们来讨论单调栈的解法：

• 1、从左到右遍历每个元素，维护一个单调递增栈，栈中存储的是 「未确定解的元素下标」，下标对应的每日温度递增；
• 2、当栈为空，将当前元素下标入栈；
• 3.1 当栈不为空，如果当前元素大于等于栈顶元素，那么循环弹出栈顶元素，直到栈为空或者当前元素小于栈顶元素；
• 3.2 当栈不为空，如果当前元素小于栈顶元素，说明当前元素小于栈内所有元素（单调性），将当前元素入栈；
• 4、元素出栈时，计算下标的差值就是间隔天数。

—— 图片引用自 LeetCode

这个问题的题解基本上就是单调栈的解题框架：

fun dailyTemperatures(T: IntArray): IntArray {
    val result = IntArray(T.size) { 0 }
    1、维护单调递增栈
    val stack = ArrayDeque<Int>()
    for (index in T.indices) {
        while (!stack.isEmpty() && T[stack.peek()] < T[index]) {
            2、弹出栈顶小于等于目标数的元素
            val preIndex = stack.pop() // 下标出栈
            result[preIndex] = index - preIndex
        }
        3、栈顶元素大于目标数，那么栈内所有元素都大于目标数（单调性）
        stack.push(index) // 下标入栈
    }
    return result
}
复制代码

提示： 你可以看下官方题解的视频讲解加深理解：【官方题解】

复杂度分析：

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

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

3. 举一反三

42. 接雨水（Hard）【题解】

84. 柱状图中最大的矩形（Hard）

402. 移掉K位数字（Medium）

496. 下一个更大元素 I（Easy）【题解】

503. 下一个更大元素 II（Medium）

739. 每日温度（Medium）【题解】

901. 股票价格跨度（Medium）

4. 总结

• 1、单调栈是在栈的基础上，利用了单调的特性，以空间换时间优化时间复杂度；
• 2、当遇到下一个更大元素（Next Greater Number ）问题时，可以考虑使用单调栈处理；
• 3、单调栈不能覆盖太大的问题域，应用价值不及其他数据结构。
• 4、单调栈还有一个孪生兄弟，你知道是什么吗？