深入理解 Python 单调栈：原理、实现与应用场景

2026-02-05 11:18:09 0条评论 3次阅读 0人点赞

在日常的算法学习或面试准备中，你可能会遇到过这样的问题：如何高效地在一个数组中找到“下一个更大的元素”，或者如何在 O(n) 的时间复杂度内解决需要重复比较的场景。如果你之前习惯使用双重循环来解决这类问题，那么今天我们将一起探索一种更优雅、更高效的数据结构技巧——单调栈。

在本文中，我们将深入探讨单调栈的核心概念。我们将通过直观的示例，学习如何在 Python 中实现它，并分析它如何将算法的时间复杂度从惊人的 O(n²) 降低到线性的 O(n)。无论你是正在准备算法面试，还是希望在处理实际数据流时优化性能，这篇文章都将为你提供实用的见解和代码实现。

什么是单调栈？

首先，让我们明确一下概念。栈是一种“后进先出”（LIFO）的数据结构，而单调栈的核心在于它对栈内元素的顺序有特定的要求：栈内的元素必须是单调递增或单调递减的。

这意味着，我们利用栈这种结构，不仅要存储数据，还要利用数据的相对大小关系来做出决策（通常是弹出元素）。这种结构在处理“Next Greater Element”（下一个更大元素）或直方图面积计算等涉及比较范围的问题时，具有奇效。

单调栈主要分为两种类型：

单调递增栈：从栈底到栈顶，元素依次增大（栈顶最小）。
单调递减栈：从栈底到栈顶，元素依次减小（栈顶最大）。

单调递增栈

让我们从最基础的单调递增栈开始。想象一下，你手里拿着一副扑克牌，你把它们叠成一摞。你的规则是：如果下一张牌比顶部的牌小，你就把顶部的牌扔掉，直到顶部的牌比下一张牌小或者没有牌为止。最后，把新牌放上去。这样，你手里的牌从下往上看就是从小到大排列的。

#### 工作原理

当我们遍历数组时，对于当前的元素 num：

检查栈是否为空。
如果栈不为空，且栈顶元素大于 num，这意味着当前元素破坏了递增的顺序。为了恢复顺序，我们需要将栈顶元素弹出。
重复步骤 2，直到栈为空或栈顶元素小于等于 num。
将 num 压入栈中。

这个过程保证了栈中的元素始终是单调递增的。值得注意的是，每当我们在 INLINECODE57fe7315 循环中弹出一个元素时，其实我们是找到了该弹出元素对应的“第一个比它小的数”（即当前的 INLINECODE05f487a0）。这是解决很多问题的关键逻辑。

#### Python 代码实现

下面是一个清晰的 Python 实现，让我们看看代码是如何工作的：

def create_increasing_stack(arr):
    """
    构建一个单调递增栈。
    返回的栈中元素从底到顶单调递增。
    """
    stack = []
    
    # 遍历输入数组中的每一个数字
    for num in arr:
        # 关键步骤：只要栈不为空，且栈顶元素大于当前元素
        # 说明为了维持单调性，栈顶元素必须“让位”（弹出）
        while stack and stack[-1] > num:
            popped_value = stack.pop()
            # 在这里，popped_value 找到了它右边第一个比它小的元素：num
            # 你可以在这里添加处理逻辑，比如记录结果
            
        # 将当前元素压入栈中，此时它比栈中剩余元素都要大或相等
        stack.append(num)
    
    return stack

# --- 示例测试 ---
input_arr = [2, 1, 2, 4, 3]
result_stack = create_increasing_stack(input_arr)
print(f"输入数组: {input_arr}")
print(f"单调递增栈结果: {result_stack}")

输出结果：

输入数组: [2, 1, 2, 4, 3]
单调递增栈结果: [1, 2, 3]

让我们通过这个例子 [2, 1, 2, 4, 3] 来模拟一下过程：

处理 INLINECODE26ce0ecc：栈空，压入 INLINECODE78ba6818。栈：[2]
处理 INLINECODE43f08776：栈顶 INLINECODE91440c6c，弹出 INLINECODEc4319dd3。栈空，压入 INLINECODE4424afbc。栈：[1]
处理 INLINECODEf41bc7f7：栈顶 INLINECODEdb5a960c，压入 INLINECODE874d67bb。栈：INLINECODEd70efc6c
处理 INLINECODE26016e77：栈顶 INLINECODE0d55feaa，压入 INLINECODE0d769ece。栈：INLINECODEb501fb44
处理 INLINECODE4fa099a9：栈顶 INLINECODE3597a456，弹出 INLINECODE7831452d；栈顶 INLINECODEba7e43c4，压入 INLINECODE22fc2052。栈：INLINECODE49fed9ee

#### 复杂度分析

你可能会问，为什么时间复杂度是 O(n)？虽然里面有一个 while 循环，但请注意，数组中的每个元素最多被压入栈一次，也最多被弹出一次。这就好比买票，每个人排一次队，买完票离开，总共的操作次数是线性的。

时间复杂度： O(n)。我们只对数组进行了一次遍历，虽然内部有循环，但每个元素的操作是常数级摊销的。
辅助空间： O(n)。最坏情况下（例如数组本身是严格递减的），栈可能需要存储所有元素。

单调递减栈

理解了递增栈，单调递减栈就很好理解了，逻辑完全相反。在这里，我们维护一个从栈底到栈顶元素依次减小的栈。这通常用于寻找“下一个更大的元素”的场景。

#### 工作原理

对于递减栈，我们在遍历时执行相反的操作：

如果栈不为空，且栈顶元素小于当前元素 num，则弹出栈顶。
重复直到栈顶元素大于等于 num 或栈为空。
压入 num。

在这个模式下，被弹出的元素找到了它右边第一个比它大的元素。

#### Python 代码实现

def create_decreasing_stack(arr):
    """
    构建一个单调递减栈。
    返回的栈中元素从底到顶单调递减。
    """
    stack = []
    
    # 遍历输入数组中的每一个数字
    for num in arr:
        # 核心逻辑：栈不为空，且栈顶元素 < 当前元素
        # 说明当前元素比栈顶大，为了维持递减顺序，需要弹出较小的栈顶元素
        while stack and stack[-1] < num:
            popped_value = stack.pop()
            # 在这里，popped_value 找到了它右边第一个比它大的元素：num
            # 这种模式常用于寻找“下一个更大元素”的问题
            
        # 将当前元素压入栈中，它现在成为了新的栈顶（最小值之一）
        stack.append(num)
    
    return stack

# --- 示例测试 ---
input_arr = [2, 1, 2, 4, 3]
result_stack = create_decreasing_stack(input_arr)
print(f"输入数组: {input_arr}")
print(f"单调递减栈结果: {result_stack}")

输出结果：

输入数组: [2, 1, 2, 4, 3]
单调递减栈结果: [4, 3]

模拟过程：

处理 INLINECODE9808745b：栈空，压入 INLINECODE28e6baf2。栈：[2]
处理 INLINECODEf0824238：INLINECODEd937ce35（满足递减，不弹），压入 INLINECODEa7e09637。栈：INLINECODE9ff4ecfd
处理 INLINECODEdedd19f4：栈顶 INLINECODEc30a387e，弹出 INLINECODEb3d83ab6；栈顶 INLINECODE7e1bfb5b，停止。压入 INLINECODEb3cd5a7d。栈：INLINECODE5ce5a95d
处理 INLINECODEfef647b9：栈顶 INLINECODEf11551dc，弹出 INLINECODE78fe0c60；栈顶 INLINECODEc57a4a6b，弹出 INLINECODE1b17b9cd；栈空。压入 INLINECODE250267b0。栈：[4]
处理 INLINECODE509e3124：INLINECODE5f1fa4df（满足递减），压入 INLINECODEfccd1f50。栈：INLINECODE126a9a94

进阶应用：寻找下一个更大元素

仅仅在栈中保留元素只是基础操作。在实际开发中，单调栈最强大的地方在于它在弹出元素的那一刻，往往意味着我们找到了该元素在某种逻辑上的“目标值”。

让我们来实现一个经典功能：对于数组中的每个元素，找到它右边第一个比它大的元素。如果找不到，则返回 -1。

这是一个典型的单调递减栈的应用。

def find_next_greater_elements(arr):
    """
    查找数组中每个元素右边第一个比它大的元素。
    使用单调递减栈来实现。
    """
    n = len(arr)
    # 初始化结果数组，默认为 -1
    result = [-1] * n
    stack = []  # 栈中存储的是元素的索引

    # 遍历数组
    for i in range(n):
        current_val = arr[i]
        
        # 如果栈不为空，且当前元素大于栈顶索引对应的元素
        while stack and current_val > arr[stack[-1]]:
            # 弹出栈顶索引
            top_index = stack.pop()
            # 记录结果：栈顶元素的下一个更大元素就是当前的 current_val
            result[top_index] = current_val
        
        # 将当前索引入栈
        stack.append(i)
    
    return result

# --- 示例测试 ---
nums = [2, 1, 2, 4, 3]
print(f"输入数组: {nums}")
print(f"下一个更大元素: {find_next_greater_elements(nums)}")

输出结果：

输入数组: [2, 1, 2, 4, 3]
下一个更大元素: [4, 2, 4, -1, -1]

在这个例子中，我们存储的是索引而不是值，这是一种更通用的做法。当我们遇到 INLINECODE0e54995b 时，它比 INLINECODEe6ce794d, INLINECODE34e8debf, INLINECODEf0211edb 都大，所以这些元素在栈中依次弹出，并将它们对应的结果位置赋值为 4。这种“批量处理”正是单调栈高效的原因。

实际应用场景与最佳实践

单调栈不仅仅是面试题的利器，在实际的工程场景中也有很多应用：

直方图中的最大矩形面积：这是单调栈最经典的应用之一。我们可以利用单调递增栈，以每根柱子的高度作为矩形的高，向左右延伸找到边界，从而计算出最大面积。
表达式求值与语法解析：编译器在处理表达式或检查括号匹配（如 INLINECODEade02856, INLINECODEe429eac9）时，也会用到类似的思想，确保结构上的平衡或优先级。
股票价格跨度问题：假设我们需要计算股票价格连续低于或等于今天价格的天数，单调递减栈可以在线性时间内解决这个问题。

常见错误与调试技巧

在实现单调栈时，你可能会遇到一些常见的坑：

边界条件：一定要检查栈是否为空 (INLINECODE255295e8)。忘记检查 INLINECODEd54f4f01 是否为空是导致 IndexError 最常见的原因。
循环条件：注意是 INLINECODE1584efcc 还是 INLINECODE0912e982（或者 INLINECODE2fecc083 vs INLINECODEc41275b9）。这决定了你是否保留相等的元素，对于结果往往有影响。
存储值还是索引：对于简单问题，存储值即可。但如果需要计算距离或返回特定位置的值，存储索引通常是更好的选择，因为它能携带更多的上下文信息。

总结

在这篇文章中，我们一步步深入探讨了 Python 中的单调栈。我们从最基本的定义出发，区分了单调递增栈和单调递减栈的区别，并通过具体的 Python 代码演示了它们的实现细节。

关键在于记住：单调栈通过牺牲空间（使用栈）来换取时间（减少重复比较）。它将原本需要嵌套循环的比较过程，转化为了线性的扫描和栈的维护。

掌握了单调栈，你就拥有了处理“下一个更大/更小元素”类问题的万能钥匙。接下来，建议你自己动手实现一下“直方图最大矩形”问题，或者尝试优化你现有的包含多重循环的代码，感受这种数据结构带来的速度提升。祝你编码愉快！

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客

深入理解 Python 单调栈：原理、实现与应用场景

什么是单调栈？

单调递增栈

单调递减栈

进阶应用：寻找下一个更大元素

实际应用场景与最佳实践

常见错误与调试技巧

总结

相关文章美国1G带宽/1T流量高速vps $17.99/年