数据结构与算法 / 系统课时

单调栈处理相邻关系

单调栈处理相邻关系

给定温度、价格或高度序列,本课解决“每个位置右侧第一个严格更大元素”问题。你将用一个保存下标的单调栈,把逐项向右扫描的 O(n2)O(n^2) 方法优化为 O(n)O(n)。

学习目标

  • 理解单调栈维护“尚未找到答案的位置”的方式
  • 掌握下一个更大元素的弹栈与回写流程
  • 说明保存下标及均摊 O(n)O(n) 的原因

单调栈如何确定相邻答案

求右侧第一个严格更大元素时,栈中保存下标,并让这些下标对应的值从栈底到栈顶单调不增。扫描到新值后,只要它大于栈顶位置的值,就说明它是该位置此前遇到的第一个更大值,可以弹栈并填写答案。

保存下标比保存数值更实用:既能从原数组取值,也能把结果写回正确位置,还能计算两个位置的距离。相等值不能触发弹栈,否则会把“相等”误判为“严格更大”。

单调栈确定下一个更大元素的流程

执行步骤

遍历下标 index 时,先持续弹出所有对应值小于当前值的栈顶下标,并将当前值写入这些位置;再把当前下标压栈。遍历结束后仍在栈中的位置,右侧不存在更大元素,保持默认答案 -1。

每个下标只会入栈一次、出栈至多一次。虽然代码包含 for 和 while,全部弹栈次数累计不超过 nn,因此时间复杂度为 O(n)O(n),额外空间复杂度为 O(n)O(n)。

主示例

以下 Python 3.9+ 示例同时返回下一个更大值和需要向右等待的距离,便于观察“保存下标”的价值。

python
def next_greater(nums: list[int]) -> tuple[list[int], list[int]]:
    greater_values = [-1] * len(nums)
    distances = [0] * len(nums)
    stack: list[int] = []

    for index, value in enumerate(nums):
        # 当前值会一次解决所有比它小的栈顶位置。
        while stack and nums[stack[-1]] < value:
            previous = stack.pop()
            greater_values[previous] = value
            distances[previous] = index - previous
        stack.append(index)

    return greater_values, distances

def main() -> None:
    values = [2, 1, 2, 4, 3]
    greater_values, distances = next_greater(values)
    print("下一个更大值:", greater_values)
    print("向右距离:", distances)

if __name__ == "__main__":
    main()

预期输出:

text
下一个更大值: [4, 2, 4, -1, -1]
向右距离: [3, 1, 1, 0, 0]

关键边界

求“更大或相等”时,弹栈条件应改为 nums[stack[-1]] <= value;求右侧第一个更小元素时,需要反转比较方向。无论目标如何变化,都应先明确栈内单调方向、触发弹栈的条件和未找到答案时的默认值。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

单调栈处理相邻关系

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通