探秘单调栈：原理、作用与应用场景全解析
探秘单调栈：原理、作用与应用场景全解析
一、单调栈是什么？
1. 回顾栈的基本概念
栈（Stack）是一种特殊的线性表，遵循先进后出（First In Last Out，简称 FILO）或后进先出（Last In First Out，简称 LIFO）的原则。通常我们把允许元素插入与删除的一端称作栈顶，另一端则是栈底。
栈的主要操作有入栈（也叫压栈、进栈）和出栈（也叫弹栈）。入栈操作是将新元素置于当前栈顶元素之上，使其成为新的栈顶；出栈操作则是移除栈顶元素，使其下方的相邻元素成为新的栈顶。
在实际代码实现中，栈可以通过数组或链表等方式来实现。无论选择哪种实现方式，入栈和出栈操作的时间复杂度都是 O(1)。不会因栈内元素数量的增加而导致操作时间大幅增长。这一特性为后续理解单调栈的操作及其优势奠定了坚实基础。
2. 单调栈的定义和分类
单调栈是一种特殊的栈结构，从字面上理解就是栈内元素具有单调性，分为单调递增栈和单调递减栈两类。
2.1 单调递增栈
定义：栈内元素按照从小到大的顺序排列，使其栈顶元素始终最小，栈底元素始终最大。
想象一下，你有一堆乱序的书本，你想把它们整理成一个整齐的书架。单调递增栈就像是你按照书本的大小，从最小的一本开始，依次往上放，这样最上面的那本书一定是最小的，而最下面的那本则是最大的。
特点：
- 栈顶的书本总是最小的。
- 栈底的书本总是最大的。
以序列 nums=[9,2,7,1,6,4,3,5] 为例，来分析一下构建一个单调递增栈的具体逻辑：
步骤1：9入栈：(9)
步骤2：2入栈：(9，2)
步骤3：2出栈，7入栈：(9，7)
步骤4：1入栈：(9，7，1)
步骤5：1出栈，6入栈：(9，7，6)
步骤6：4入栈：(9，7，6，4)
步骤7：3入栈：(9，7，6，4，3)
步骤8：3出栈，4出栈，5入栈：(9，7，6，5)
💡单调递减栈入栈过程（入栈元素为e）
从栈顶元素开始遍历，弹出栈中所有小于等于 e 的元素，直到栈为空或者遇到第一个大于 e 的元素为止，最后将元素 e 压栈。
2.2 单调递减栈
定义：栈内元素按照从大到小的顺序排列，使其栈顶元素始终最大，栈尾元素始终最小。
还是那堆乱序的书本，但这次你想换个方式整理。单调递减栈就像是你从最大的一本书开始放，然后依次放较小的书，直到最上面放的是最小的那本。
特点：
- 栈顶的书本总是最大的。
- 栈底（也就是最后放上去的那本）的书本总是最小的。
还是以序列 nums=[9,2,7,1,6,4,3,5] 为例，这次来分析一下构建一个单调递减栈的思路：
步骤1：9入栈：(9)
步骤2：9出栈，2入栈：(2)
步骤3：7入栈：(2，7)
步骤4：7出栈，2出栈，1入栈：(1)
步骤5：6入栈：(1，6)
步骤6：6出栈，4入栈：(1，4)
步骤7：4出栈，3入栈：(1，3)
步骤8：5入栈：(1，3，5)
💡单调递减栈入栈过程（入栈元素为e）
从栈顶开始遍历，弹出栈中所有大于等于 e 的元素，直到栈为空或者遇到第一个小于 e 的元素为止，最后将元素 e 压栈。
二、单调栈常见的应用场景
1. 在数组中找下一个较大（或较小）元素
在实际的算法问题中，寻找给定数组中每个元素的下一个较大或较小元素是一种常见需求。单调栈在这类问题中显得尤为高效。
1.1 寻找下一个较大元素
以数组 [5, 3, 8, 2, 7, 1] 为例，我们可以使用单调递减栈来找出每个元素的下一个较大元素。
解决思路：
- 初始化：创建一个空栈，并准备一个与输入数组等长的结果数组，初始值可以设定为 -1（表示没有找到较大元素）。
- 遍历数组：从左到右遍历数组，逐个处理每个元素。
- 若栈为空，将当前元素的下标加入栈。
- 若当前元素大于栈顶元素，弹出栈顶元素并记录其下一个较大元素为当前元素，重复此步骤，直到当前元素小于等于栈顶元素。（即将栈中所有小于当前元素的下标弹出）
- 将当前元素的下标入栈。
- 处理完成：遍历完整个数组后，结果数组即为每个元素的下一个较大元素。如果栈中还有元素，说明这些元素右侧没有较大元素，结果数组中的值保持为 -1。
还是以数组 [5, 3, 8, 2, 7, 1] 为例，具体的处理过程如下：
步骤1：初始栈为空，遍历到 5，入栈。
步骤2：遍历到 3，3 小于栈顶元素 5，入栈。
步骤3：遍历到 8，8 大于栈顶元素 3，弹出 3，记录 3 的下一个较大元素为 8，然后继续弹出 5，记录 5 的下一个较大元素也是 8，最后将 8 的下标入栈。
步骤4：遍历到 2，2 小于栈顶元素 8，入栈。
步骤5：遍历到 7，7 大于栈顶元素 2，弹出 2，记录 2 的下一个较大元素为 7，然后入栈 7。
步骤6：遍历到 1，1 小于栈顶元素 7，入栈。
最终结果为 [8, 8, -1, 7, -1, -1]。
1.2 寻找下一个较小元素
寻找下一个较小元素的思路类似，但此时需要构建单调递增栈。对于同样的数组 [5, 3, 8, 2, 7, 1]，处理逻辑如下：
解决思路：
- 初始化：创建空栈和结果数组，初始值同样设定为 -1。
- 遍历数组：从左到右遍历元素。
- 与找下一个较大元素的方式相同，若当前元素小于栈顶元素，则弹出栈顶元素，并记录其下一个较小元素为当前元素。
- 否则，将当前元素的下标入栈。
- 完成处理：遍历结束后，结果数组即为每个元素的下一个较小元素。
与暴力解法相比，暴力解法往往需要双重循环遍历数组来进行比较，时间复杂度为 O(n²)。而利用单调栈只需遍历一遍数组，因此时间复杂度优化至 O(n)，这在处理大规模数据时显著提升了效率。
2. 柱状图中求最大矩形面积
在处理柱状图相关问题时，给定的 n 个非负整数表示柱子的高度，每个柱子彼此相邻且宽度为 1。我们的目标是求出在该柱状图中能够形成的最大矩形面积。使用单调栈是一种非常有效的解题思路。
解决思路：
- 初始化：在原数组的首尾插入 0，以便于计算边界（在左侧添加 0 便于处理左边界，右侧添加 0 确保栈中所有元素都能出栈）。这样，输入数组 [2, 1, 5, 6, 2, 3] 变为 [0, 2, 1, 5, 6, 2, 3, 0]。
- 遍历数组：维护一个单调递增栈，栈中存放柱子的下标。遍历过程中，当遇到的柱子高度小于栈顶柱子的高度时，说明栈顶柱子找到了右边界，此时进行以下操作：
- 出栈栈顶元素，得到当前柱子的高度。
- 计算矩形的宽度：右边界为当前下标，左边界为栈顶元素的下一个位置（即出栈前的栈顶元素）。
- 使用公式计算面积：面积 = 高度 × 宽度。
- 更新最大面积：在遍历过程中不断更新记录到的最大矩形面积。
以数组 [2, 1, 5, 6, 2, 3] 为例，具体步骤如下：
步骤 1：开始时栈为空，将第一个元素 0 的下标 0 入栈。
步骤 2：将 2 的下标 1 入栈，因为 2 大于栈顶元素 0，满足入栈条件。
步骤 3：将 1 的下标 2 入栈，此时 1 小于栈顶元素 2，说明 2 的右边界找到了。将 2 出栈，计算以 2 为高的矩形面积，左边界为 0，宽度为 (2 - 0 - 1) = 1，因此面积为 2 × 1 = 2。
步骤 4：继续遍历，将 5 的下标 3 和 6 的下标 4 分别入栈。当遇到 2 时，2 小于栈顶元素 6，出栈并计算以 6 为高的矩形面积，左边界为 3，宽度为 (5 - 3 - 1) = 1，因此面积为 6 × 1 = 6。
步骤 5：继续处理剩余元素，直到遍历完整个数组。
常规的双指针法等暴力解法通常需要较高的时间复杂度，可能导致超时。而利用单调栈的解法可以将时间复杂度优化到 O(n)，高效地解决最大矩形面积问题。
3. 处理字符串相关问题（如删除重复字母）
在一些字符串处理问题中，单调栈也有其巧妙的应用，例如删除字符串中的重复字母，以得到字典序最小的字符串。
以字符串 "bcabc" 为例，我们的目标是去除其中的重复字母，同时确保最终结果的字典序最小，且不改变字符的相对位置。
解决该问题可以分为两个主要步骤：去重和保持字典序。具体实现逻辑如下：
- 初始化数据结构：
- 创建一个 charCount 数组，用于记录每个字符在字符串中出现的次数。
- 创建一个 isUsed 布尔数组，用于标记当前字符是否已经在栈中。
- 使用一个栈来存放最终结果中的字符。
- 遍历字符串：
- 首先，统计每个字符的出现次数，并初始化 isUsed 布尔数组。
- 然后，遍历字符串的每个字符，执行以下操作：
- 如果当前字符已经在栈中（即 isUsed 数组为真），则跳过该字符。
- 否则，判断当前字符与栈顶元素的字典序关系：
- 如果当前字符小于栈顶元素，并且栈顶元素在后续还有出现（通过 charCount 数组判断），则弹出栈顶元素。
- 将当前字符压入栈中，并更新 isUsed 数组和 charCount 数组。
- 构建最终结果：
- 遍历完整个字符串后，栈中的元素即为最终结果，依次弹出并连接成字符串。
以字符串 "bcabc" 为例，
步骤1：初始化 charCount = {'b': 2, 'c': 2, 'a': 1}，isUsed = {b: false, c: false, a: false}，栈为空。
步骤2：遍历到 b，将 b 压入栈，标记 isUsed[b]=true。
步骤3：遍历到 c，c 大于栈顶元素 b，将 c 压入栈，标记 isUsed[c]=true。
步骤4：遍历到 a，a 小于栈顶元素 c，且 c 还有出现，因此弹出 c，然后将 a 压入栈，更新相应标记。
步骤5：遍历到 b，b 小于栈顶元素 a（但 a 在后面没有剩余），直接将 b 压入栈。
步骤6：遍历到 c，c 大于栈顶元素 b，将 c 压入栈。
最终栈中的元素顺序为 a,b,c，依次弹出得到字符串 "abc"，满足删除重复字母且字典序最小的要求。通过单调栈这种巧妙的筛选机制，能够帮助我们在处理这类字符串相关问题时，更合理地保留合适的字母，高效地达到题目所要求的效果。
三、单调栈应用与实践
654. 最大二叉树
采用单调栈的基本思路是这样的：
- 如果栈顶元素大于待插入的元素，那么直接入栈。
- 如果栈顶元素小于待插入的元素，那么栈顶元素出栈。
当然，在对比两个节点大小和出入栈的同时，依然还是会根据题意，进行二叉树的构造。即：
- 如果栈顶元素大于待插入的元素，则：栈顶元素.right = 待插入元素。
- 如果栈顶元素小于待插入的元素，则：待插入元素.left = 栈顶元素。
我们依然以 nums=[3,2,1,6,0,5] 为例，看一下通过单调栈是怎么创建二叉树的。首先，对于数组中的前三个元素，满足 Node(3) > Node(2) > Node(1)，所以这三个元素直接入栈，并且构造二叉树 Node(3).right = Node(2); Node(2).right = Node(1) 具体操作，如下图所示：
当我们遍历到Node(6)的时候，由于 Node(1) 小于 Node(6) ，所以 Node(1) 出栈，并且执行Node(6).left = Node(1)；由于 Node(2) 也小于 Node(6)，所以 Node(2) 也执行出栈操作，并执行并且执行 Node(6).left = Node(2)；
注意：此时 Node(6) 的左子树节点从 Node(1) 变为了 Node(2)；由于 Node(3) 也小于 Node(6)，所以 Node(3) 也执行出栈操作，并执行并且执行 Node(6).left = Node(3)；
注意：此时 Node(6) 的左子树节点从 Node(2) 变为了 Node(3)；由于栈中元素都出栈了，没有可以跟 Node(6) 进行对比的元素了，此时 Node(6) 入栈，本次操作完毕。具体操作，如下图所示：
我们继续遍历到 Node(0)，由于 Node(0) 小于栈顶元素Node(6)，所以Node(0) 直接入栈就可以了。但别忘记维护一下二叉树，也就是说，配置一下 Node(6).right = Node(0)。具体操作，如下图所示：
最后，我们遍历到了 Node(5)，由于 Node(5) 大于当前栈顶元素 Node(0)，所以 Node(0) 执行出栈操作，并维护二叉树结构 Node(5).left = Node(0)；在对比 Node(5) 小于当前栈顶元素 Node(6)，所以，Node(5) 直接入栈即可。维护二叉树结构 Node(6).right = Node(5)。具体操作，如下所示：
// 单调栈(递增)
func constructMaximumBinaryTree(nums []int) *TreeNode {
if nums == nil || len(nums) == 0 {
return nil
}
var stack []*TreeNode
for i := 0; i < len(nums); i++ {
node := &TreeNode{Val: nums[i]}
for len(stack) > 0 {
// 获取栈顶元素
top := stack[len(stack)-1]
// 如果栈顶元素大于待插入元素, 直接入栈
if top.Val > node.Val {
stack = append(stack, node)
top.Right = node
break
}
// 出栈
stack = stack[:len(stack)-1]
node.Left = top
}
if len(stack) == 0 {
stack = append(stack, node)
}
}
return stack[0]
}
参考文章：654. 最大二叉树 - 力扣（LeetCode）