单调栈导论

栈是一种基本的数据结构，在编程和算法中被广泛使用。它遵循后进先出（LIFO）原则，允许进行入栈（push）和出栈（pop）操作，但不能直接访问中间的元素。单调栈是标准栈的一个变体，增加了一个额外的规则——元素必须严格递增或递减。与普通栈不同，入栈一个元素可能需要重新排列现有元素以保持单调顺序。单调栈可以为涉及查找序列中每个元素的下一个更大或更小元素的问题提供高效的 O(n) 解决方案。本文将介绍 Python 中的单调栈，包括其动机、实现、时间复杂度分析以及在下一个更大元素和直方图中最大矩形等问题中的应用。我们将探讨递增和递减单调栈，以及如何维护单调规则可以加速某些算法。

什么是单调栈？

单调栈是一种常规栈数据结构的变体，它额外增加了一个约束：元素必须严格递增或递减。

当将一个新元素压入单调栈时，它会与栈顶的现有元素进行比较，只有在弹出所有违反单调顺序的现有元素后，新元素才会被压入。例如，在递增单调栈中，会先弹出较小的元素，然后再压入新元素。

这确保了对于递增（或递减）单调栈，新元素总是大于（或小于）栈中现有元素。

维护这种单调不变性可以高效地解决以下问题：

• 下一个更大元素 - 查找每个元素的下一个更大元素
• 前一个更小元素 - 查找前一个更小元素
• 股票跨度 - 元素比前几天大的天数
• 直方图中最大矩形 - 直方图中最大面积矩形

相比之下，不使用单调栈时，这些问题需要对每个元素进行 O(n^2) 的比较。

单调栈允许跟踪“相关”元素，从而以最优的 O(n) 时间计算这些问题的答案。因此，它是某些优化和算法问题的一个强大概念。

单调栈的性质

• 排序顺序 - 单调栈的定义性不变性是元素从底部到顶部按升序或降序排序。入栈新元素时，会弹出较小/较大的元素以保持顺序。
• LIFO 操作 - 作为栈的变体，单调栈只允许入栈和出栈操作。元素只能以 LIFO 的方式从栈顶插入/移除。不提供其他访问方式。
• 单一排序方向 - 单调栈保持单一排序方向——递增或递减。它不能同时保持升序和降序的元素。方向取决于用例。
• 非唯一元素 - 与典型的排序数据结构不同，单调栈允许重复的元素值。但是，它们的相对顺序仍然根据插入顺序来维护。
• 摊销 O(1) 操作 - 单个入栈/出栈操作可能需要 O(n) 时间，如果弹出很多元素，但在一系列操作中，它的摊销时间为 O(1)。类似于动态数组。
• 空间效率 - 单调栈空间效率高，除了大小为 n 的输入数组外，只需要 O(n) 的额外空间。远少于排序数组。
• 在线处理 - 它可以逐步处理流中的元素，而无需查看未来的元素。适用于在线算法。
• 重置关系 - 新的最大值或最小值会重置从那时起的相关比较和关系。不保留完整历史记录。
• 无随机访问 - 不支持直接随机访问。仅支持基于 LIFO 的顺序入栈/出栈访问。
• 通用数据 - 可与任何可比较的数据类型配合使用，如数字、字符串等。不局限于数字。

单调栈与普通栈的区别

普通栈和单调栈之间的主要区别在于：

• 排序 - 普通栈的元素没有排序。单调栈保持升序或降序。
• 入栈操作 - 在普通栈中，入栈始终是 O(1)。在单调栈中，如果弹出元素以维持顺序，入栈最坏情况下可能为 O(n)，但在连续操作中摊销为 O(1)。
• 出栈操作 对于普通栈和单调栈均为 O(1)。
• 查看操作 - 查看操作对于两者均为 O(1)。返回顶部元素。
• 元素访问 - 普通栈允许对任何元素进行随机访问。单调栈仅允许以 LIFO 顺序进行顺序入栈/出栈访问。
• 应用 - 普通栈用于反转顺序、跟踪状态等。单调栈用于在序列中查找上一个/下一个重要元素。
• 空间复杂度 - 对于 n 个元素的序列，两者都需要 O(n) 的额外空间。
• 实现 - 单调栈只需要几行额外的代码来在入栈时检查/维护顺序。

总之，单调栈与普通栈的唯一区别在于维护排序顺序，同时具有相似的 LIFO 访问。这种排序允许高效的算法在序列中查找相对更大/更小的元素。

单调栈的优势

• 最优时间复杂度 - 像下一个更大/更小元素、股票跨度等问题，使用单调栈的朴素方法可以在 O(n) 时间内解决，而无需 O(n^2) 的时间。维护排序顺序允许跟踪有用的元素来计算答案。
• 空间效率高 - 单调栈只需要 O(n) 的额外空间和输入数组。不需要额外的数据结构。
• 易于实现 - 通过修改常规栈的几行代码来检查/在入栈时维护排序顺序，可以轻松实现单调栈。
• 通用性强 - 递增和递减变体都可以用于解决不同的问题。递增顺序在向前看时有用，递减顺序在向后看时有用。
• 仅保留相关元素 - 单调栈只保留在任何时候都对查找解决方案有用的元素；其余的都弹出。它比保留完整的窗口节省了空间和计算。
• 无需完整排序/扫描 - 与某些解决方案不同，不需要对数组进行完全排序或扫描。入栈/出栈操作会处理排序。
• 缓存友好 - 元素访问是顺序的，而不是其他结构中的随机访问。更好地利用 CPU 缓存。
• 易于理解 - 单调变体使得在实现过程中逻辑/流程易于理解和推理。

总的来说，单调不变性使得算法非常高效，可以与一些高级数据结构相媲美，同时又足够简单，可以快速编码。这是一个优雅而强大的概念！

单调栈的不同应用

• 下一个更大元素 - 查找数组中每个元素的下一个更大元素。使用递增单调栈可以得到 O(n) 的解决方案。在涉及查找更大元素的这类问题中很有用。
• 前一个更小元素 - 使用递减单调栈可以在 O(n) 时间内查找每个元素的前一个更小元素。在金融分析中有所应用。
• 股票跨度问题 - 计算每天的跨度——连续价格上涨的天数。单调栈可以提供最优解决方案。
• 直方图中最大矩形 - 从连续条形的高度中找到可能的直方图中最大矩形面积。使用递减单调栈的 O(n) 解决方案。
• 表达式求值 - 单调栈可以以所需的最少操作次数来求值表达式。用于计算器算法。
• 最近较小值 - 查找数组元素左侧和右侧最近的较小值。单调栈可以在线性时间内完成。
• 接雨水 - 计算条形高度之间捕获的总水量。使用两个单调栈高效解决。
• 最长递增子序列 - 单调栈有助于重建每个索引处结束的最长递增子序列。
• 最近较大值 - 在线性时间内找到每个元素左右两侧最近的较大元素。

总而言之，单调栈在高效查找序列中上一个或下一个重要元素的这类问题中表现出色。有序的结构允许跟踪有用的元素，从而以最优的时间计算答案。

递增单调栈

递增单调栈从底部到顶部维护严格递增的元素。关键属性是：

• 压入的新元素总是大于现有元素。为了保持顺序，会弹出较小的元素。
• 通过入栈/出栈操作遵循后进先出（LIFO）顺序。
• 在最坏情况下，如果需要多次出栈，入栈需要 O(n) 时间，但在连续操作中摊销为 O(1)。
• 查找每个元素的下一个更大元素需要 O(n) 时间。
• 在序列中向前查找较大元素时有用。
• 应用包括下一个更大元素、股票跨度、表达式求值等。

入栈伪代码

递减单调栈

递减单调栈从底部到顶部维护严格递减的元素。关键属性是：

• 压入的新元素总是小于现有元素。会弹出较大的元素。
• 它也遵循后进先出（LIFO）的访问顺序。
• 入栈最坏情况下需要 O(n) 时间，但在连续操作中摊销为 O(1)。
• 查找前一个更小元素需要 O(n) 时间。
• 在序列中向后查找较小元素时有用。
• 应用包括前一个更小元素、直方图中最大矩形等。

入栈伪代码

总而言之，递增单调栈向前看，递减栈向后看。两者都通过动态维护排序顺序为它们的问题提供高效的 O(n) 解决方案。

Python 实现

严格递增单调栈

1. 创建一个 MonotonicStack 类来表示栈。有一个空的 'items' 列表来存储元素。
2. 定义 isEmpty() 方法来检查栈是否为空。只需检查 items 列表是否为空，将其与 [] 进行比较。
3. 定义 peek() 方法来返回栈顶元素。使用索引 len(items)-1 返回 items 列表的最后一个元素。
4. 定义 push(x) 方法来压入新元素 x，方法是：
5. a) 循环，直到栈为空或栈顶元素小于 x
6. b) 在循环内部，通过调用自定义的 pop() 方法弹出元素
7. c) 循环结束后，将 x 追加到 items 列表
8. 定义 pop() 方法来弹出栈顶元素
9. a) 检查栈是否为空
10. b) 使用 del 和索引 len(items)-1 从 items 列表中移除最后一个元素
11. 定义 printStack() 方法来打印 items 列表以进行调试。
12. 关键步骤是在 push() 中检查顺序，并在 pop() 中移除最后一个元素。
13. 这些步骤共同维护了在元素入栈或出栈时的递增顺序。
14. 没有使用 Python 列表方法，如 append() 或 pop()。

该算法通过在入栈前迭代和比较元素来手动强制执行单调顺序。出栈只是移除最后一个元素。

输出

严格递减单调栈

1. 创建 MonotonicStack 类来表示带有空 items 列表的栈
2. 定义 isEmpty() 方法来检查栈是否为空。将 items 与 [] 进行比较
3. 定义 peek() 来返回栈顶元素。使用索引返回 items 列表的最后一个元素。
4. 定义 push(x) 方法来压入新元素 x
5. a) 循环，直到栈为空或栈顶元素大于 x
6. b) 在循环内部，通过调用自定义的 pop() 方法弹出元素
7. c) 循环结束后，将 x 追加到 items 列表
8. 定义 pop() 方法来移除栈顶元素
9. a) 检查栈是否为空
10. b) 使用索引从 items 中移除最后一个元素
11. 定义 printStack() 来打印 items 列表
12. 关键步骤是：
13. a) 通过与栈顶比较来检查 push() 中的顺序
14. b) 在追加 x 之前弹出较大的元素
15. c) 在 pop() 中移除最后一个元素
16. 这些步骤在入栈和出栈时强制执行递减顺序。
17. 没有使用 Python 列表方法，如 append()/pop()。
18. 通过在追加之前迭代和比较元素来维护顺序。

通过修改 push() 中的顺序检查，我们可以在没有预定义函数的情况下实现递减单调栈。

输出