单调栈数据结构应用：快速求解下一个更大元素问题

一、从一个常见的面试题说起

想象一下这样一个场景：你拿到了一串数字，比如 [2, 1, 5, 6, 2, 3]，你的任务是，为每一个数字，找到在它右边第一个比它大的数字。如果右边没有更大的数字，就返回一个特殊值（比如 -1）来表示。

这个就是经典的“下一个更大元素”问题。乍一看似乎很简单，不就是两层循环遍历吗？对每个数字，都往右扫描，直到找到第一个比它大的。这种方法我们称之为“暴力解法”。它的时间复杂度是 O(n²)，当数组长度很大时（比如有10万个数字），效率会非常低，可能会让你的程序“卡住”。

那么，有没有一种更聪明、更快速的方法呢？答案是肯定的。今天我们要介绍的主角——单调栈，就是解决这类问题的“神兵利器”。它可以把时间复杂度降到 O(n)，意味着即便处理海量数据，也能飞快得出结果。

二、什么是单调栈？它为什么这么快？

“栈”这个数据结构大家应该不陌生，就像一摞盘子，后放上去的盘子（后进）会先被拿走（先出）。而“单调栈”，就是在普通栈的基础上，加了一条额外的规则：栈里面的元素必须保持单调性（要么从栈底到栈顶单调递增，要么单调递减）。

对于“下一个更大元素”这个问题，我们通常维护一个从栈底到栈顶单调递减的栈。为什么这样设计呢？让我们用生活的例子来理解：

你可以把数组想象成一列排队的人，他们的身高就是数组里的数字。我们要为每个人找在他后面第一个比他高的人。

我们用一个栈来记录“还没有找到后面更高者”的人。
从队伍开头（数组开头）开始，让人依次入栈。
当一个新人准备入栈时，我们拿他和栈顶的人（最后进入等待队列的人）比身高。
- 如果新人比栈顶的人高，那么恭喜栈顶的人！他找到了他后面第一个比他高的人，就是这个新人。记录结果后，栈顶的人就可以“安心离开”（出栈）了。
- 接着，我们继续用新人和新的栈顶比较，直到新人比栈顶矮，或者栈空了为止。
- 最后，让这个新人入栈，等待属于他的那个“更高的人”。

这个过程确保了栈里等待的人，身高一定是越靠近栈顶越矮（单调递减）。因为一旦来了一个更高的人，就会把前面比他矮的人都“解决”掉。这样，每个元素都只会进栈一次、出栈一次，我们只需要沿着数组遍历一遍，所有问题就都解决了，效率自然就高了起来。

三、手把手演示：看单调栈如何工作

光说原理可能有点抽象，我们直接用一个完整的例子，把每一步都画出来（虽然这里用文字描述，但请你尽量在脑中想象）。我们使用的技术栈是 Python，因为它语法清晰，易于理解。

假设数组是 nums = [3, 1, 4, 2, 5]，我们需要为每个元素找到下一个更大元素。

# 技术栈：Python
def nextGreaterElement(nums):
    """
    使用单调栈寻找数组中每个元素的下一个更大元素。
    
    参数:
        nums: 输入的数字列表
    
    返回:
        result: 一个列表，result[i] 是 nums[i] 的下一个更大元素，没有则返回 -1
    """
    length = len(nums)
    result = [-1] * length  # 初始化结果列表，默认-1表示没找到
    stack = []              # 单调栈，栈里存放的是元素的索引，而不是值，方便定位
    
    # 开始遍历数组
    for i in range(length):
        current_num = nums[i]
        
        # 核心逻辑：当栈不为空，且当前元素大于栈顶索引对应的元素时
        while stack and current_num > nums[stack[-1]]:
            # 栈顶元素找到了它的“下一个更大元素”，就是当前的 current_num
            top_index = stack.pop()      # 弹出栈顶索引
            result[top_index] = current_num # 记录结果
            
        # 当前元素的索引入栈，等待后面有人来“拯救”它
        stack.append(i)
    
    # 遍历结束后，栈里剩下的元素，右边都没有更大的元素了，结果保持为-1
    return result

# 示例运行
nums = [3, 1, 4, 2, 5]
ans = nextGreaterElement(nums)
print(f"输入数组: {nums}")
print(f"下一个更大元素: {ans}")
# 输出: 输入数组: [3, 1, 4, 2, 5]
# 输出: 下一个更大元素: [4, 4, 5, 5, -1]

让我们一步步拆解，看看循环是如何进行的：

i=0, num=3: 栈空，索引0入栈。栈 [0]，结果 [-1, -1, -1, -1, -1]
i=1, num=1: 1 不大于栈顶 nums[0]=3，索引1入栈。栈 [0, 1]
i=2, num=4: 4 大于栈顶 nums[1]=1 → 弹出索引1，result[1] = 4。栈变为 [0]。
- 继续：4 大于栈顶 nums[0]=3 → 弹出索引0，result[0] = 4。栈空。
- 索引2入栈。栈 [2]，结果 [4, 4, -1, -1, -1]
i=3, num=2: 2 不大于栈顶 nums[2]=4，索引3入栈。栈 [2, 3]
i=4, num=5: 5 大于栈顶 nums[3]=2 → 弹出索引3，result[3] = 5。栈变为 [2]。
- 继续：5 大于栈顶 nums[2]=4 → 弹出索引2，result[2] = 5。栈空。
- 索引4入栈。栈 [4]，结果 [4, 4, 5, 5, -1]
循环结束：栈里剩下索引4，对应 nums[4]=5，右边没有元素了，所以 result[4] 保持为 -1。

通过这个详细的推演，你应该能清晰地看到，单调栈如何巧妙地利用“后入先出”和“单调性”，在一次遍历中高效地完成了配对工作。

四、不仅仅是数组：更复杂的应用场景

单调栈的魅力在于它的模式非常通用。一旦你掌握了“为每个元素寻找下一个更大/更小元素”这个核心思想，很多看似不同的问题都能迎刃而解。

场景一：每日温度 这是LeetCode上一个经典问题：给定一个每日温度列表，你需要计算对于每一天，至少要等多少天才能等到更暖和的温度。这本质上就是找“下一个更大元素”，不过结果不是那个更大的值，而是两个索引的距离（天数差）。我们只需要稍微修改一下记录结果的逻辑即可。

# 技术栈：Python
def dailyTemperatures(temperatures):
    """
    计算需要等待更暖温度的天数。
    
    参数:
        temperatures: 每日温度列表
    
    返回:
        answer: 列表，answer[i] 表示第 i 天后需要等待的天数
    """
    n = len(temperatures)
    answer = [0] * n  # 默认等待0天（实际上找不到就是0）
    stack = []        # 单调递减栈，存索引
    
    for i in range(n):
        current_temp = temperatures[i]
        # 当当前温度高于栈顶那天的温度时
        while stack and current_temp > temperatures[stack[-1]]:
            prev_index = stack.pop()          # 之前更冷的那天
            answer[prev_index] = i - prev_index # 计算天数差并记录
        stack.append(i)
    return answer

# 示例
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(f"每日温度: {temps}")
print(f"等待天数: {dailyTemperatures(temps)}")
# 输出: 等待天数: [1, 1, 4, 2, 1, 1, 0, 0]
# 解读：第0天(73度)，1天后升温到74度。第2天(75度)，4天后升温到76度。

场景二：柱状图中的最大矩形 这是一个更高级的应用。给定一个代表柱状图高度的数组，求图中能勾勒出的最大矩形的面积。解决这个问题的关键思路是：确定以每一根柱子为高度的矩形，最大能向左向右延伸多宽。而“延伸的边界”，恰恰就是左边和右边第一个比当前柱子矮的柱子位置——这正好可以用两次单调栈（一次找左边第一个更小，一次找右边第一个更小）来高效求得。虽然代码比前两个例子稍长，但核心依然是单调栈。

# 技术栈：Python
def largestRectangleArea(heights):
    """
    计算柱状图中能勾勒出的最大矩形面积。
    
    参数:
        heights: 柱状图的高度列表
    
    返回:
        max_area: 最大矩形面积
    """
    n = len(heights)
    # 我们需要找到每个柱子左边和右边第一个比它矮的柱子的位置
    left_bound = [0] * n    # 左边界索引
    right_bound = [n] * n   # 右边界索引，默认是n（最右端外）
    stack = []              # 单调递增栈（从栈底到栈顶高度递增）
    
    # 第一次遍历，找到右边界
    for i in range(n):
        # 当当前柱子比栈顶柱子矮时，当前柱子就是栈顶柱子的右边界
        while stack and heights[i] < heights[stack[-1]]:
            top_index = stack.pop()
            right_bound[top_index] = i
        stack.append(i)
    
    stack.clear() # 清空栈，用于第二次遍历
    
    # 第二次遍历，找到左边界（从右往左遍历逻辑类似，也可以从左往右用类似找右边界的方法）
    # 这里采用从左往右的标准写法，逻辑和找右边界对称
    for i in range(n):
        # 当当前柱子比栈顶柱子矮时，栈顶柱子是当前柱子左边第一个更矮的吗？不，我们需要反着来。
        # 更直观的方式是：维护单调递增栈，当元素被弹出时，新的栈顶就是它左边第一个比它小的索引
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left_bound[i] = stack[-1] if stack else -1 # 栈空则左边界为-1（最左端外）
        stack.append(i)
    
    # 计算最大面积
    max_area = 0
    for i in range(n):
        # 宽度 = 右边界 - 左边界 - 1
        width = right_bound[i] - left_bound[i] - 1
        area = width * heights[i]
        max_area = max(max_area, area)
    
    return max_area

# 示例
heights = [2, 1, 5, 6, 2, 3]
print(f"柱状图高度: {heights}")
print(f"最大矩形面积: {largestRectangleArea(heights)}")
# 输出: 最大矩形面积: 10 (以高度5和6的柱子为中心，宽度为2，高度为5，面积10)

五、技术的优缺点与使用注意事项

任何技术都有其适用边界，单调栈也不例外。

优点：

效率极高：对于“下一个更大/更小元素”这类问题，它能将时间复杂度从暴力解的 O(n²) 优化到 O(n)，因为每个元素最多入栈和出栈各一次。
思路清晰：一旦理解其维护单调性的核心思想，代码模板相对固定，容易记忆和实现。
应用广泛：是解决一系列特定区间和边界问题的有力工具，尤其在算法竞赛和面试中常见。

缺点与注意事项：

适用场景特定：它主要擅长解决与“邻近比较”和“边界确定”相关的问题。如果问题不具备这种局部单调特性，强行使用可能适得其反。
边界条件容易出错：栈为空时的判断、结果是存值还是存索引、初始化值设为多少（0还是-1），这些细节需要根据具体题目仔细处理，否则极易产生错误。
单调性的方向需要仔细分析：是维护递增栈还是递减栈？这取决于问题是找“更大”还是“更小”。需要根据题意准确判断，可以通过画简单例子来验证。
空间复杂度：需要额外的栈空间，最坏情况下（如数组完全单调递减）所有元素都会入栈，空间复杂度为 O(n)。但在时间复杂度大幅优化的前提下，这个空间开销通常是可接受的。

六、总结与进阶思考

单调栈是一种非常精妙的数据结构应用，它把“空间换时间”和“利用历史信息”的思想发挥到了极致。它教会我们，有时候不需要蛮力地重复扫描，通过维护一个具有特定性质（单调性）的辅助结构，可以高效地获取我们需要的信息。

掌握单调栈，不仅仅是学会了一个算法模板，更是培养了一种对数据顺序和局部关系的敏感性。当你遇到需要为每个元素寻找特定边界（更大、更小、第一个满足某种条件的元素）的问题时，不妨先思考一下：能否用一个栈来维护一个待解决的序列？这个序列的单调性是什么？

希望这篇博客能帮你彻底理解单调栈的原理和应用。建议你找一些相关的题目（如“接雨水”、“股票跨度问题”等）动手练习，巩固这一强大的工具。记住，看懂和写出无BUG的代码之间，还隔着大量的练习。

敲码拾光专注于编程技术，涵盖编程语言、代码实战案例、软件开发技巧、IT前沿技术、编程开发工具，是您提升技术能力的优质网络平台。