30 秒速览

  • 什么时候用：括号匹配、表达式求值、需要记住最近状态、单调性问题
  • 核心特性：后进先出（LIFO）
  • 时间复杂度：push/pop O(1)
  • 空间复杂度：O(n)

一、直觉建立

洗盘子

想象你在洗盘子时把盘子摞成一摞：

  • 洗完一个盘子，放在最上面（push）
  • 用盘子时，只能从最上面拿（pop）
  • 后进先出 LIFO（Last In First Out）

LIFO 的本质：栈就像一条死胡同，先进去的人被堵在最里面，后进去的人反而先出来。

栈的核心价值

记忆最近的状态，处理嵌套结构

情景：你在图书馆找书（深度优先探索）
1. 拿了书 A                    stack = [A]
2. A 引用了 B，去找 B          stack = [A, B]
3. B 引用了 C，去找 C          stack = [A, B, C]
4. 看完 C，回到 B              stack = [A, B]
5. 看完 B，回到 A              stack = [A]
6. 看完 A，完成                stack = []

栈保存了"回溯路径"：后遇到的问题先处理

生活中的栈

生活场景编程对应
浏览器后退按钮页面访问历史
Ctrl+Z 撤销编辑器命令栈
函数调用调用栈
括号配对嵌套结构

Python 中的栈

stack = []
stack.append(1)       # push - 入栈
stack.append(2)
top = stack[-1]       # peek - 查看栈顶
val = stack.pop()     # pop - 出栈
is_empty = len(stack) == 0

二、典型例题

例题 1：LC 20. 有效的括号

题目：给定一个只包括括号的字符串 s，判断字符串是否有效。

示例：

输入：s = "()[]{}"
输出：true

输入：s = "([)]"
输出：false

思路

括号匹配的规律：

  1. 左括号必须有对应的右括号
  2. 最近的左括号与当前的右括号配对（LIFO）
过程演示：s = "([{}])"

遇到 '(' → stack = ['(']
遇到 '[' → stack = ['(', '[']
遇到 '{' → stack = ['(', '[', '{']
遇到 '}' → 栈顶是 '{'，配对！stack = ['(', '[']
遇到 ']' → 栈顶是 '['，配对！stack = ['(']
遇到 ')' → 栈顶是 '('，配对！stack = []

最后栈空，有效！

代码

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for c in s:
        if c in pairs:  # 右括号
            if not stack or stack.pop() != pairs[c]:
                return False
        else:  # 左括号
            stack.append(c)

    return len(stack) == 0

复杂度：时间 O(n)，空间 O(n)

例题 2：LC 739. 每日温度

题目：给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请用 0 来代替。

示例：

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

思路：单调栈

维护一个单调递减栈，存储温度的索引。

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

i=0, t=73: stack=[0]
i=1, t=74: 74>73, 弹出0, answer[0]=1-0=1, stack=[1]
i=2, t=75: 75>74, 弹出1, answer[1]=2-1=1, stack=[2]
i=3, t=71: 71<75, stack=[2,3]
i=4, t=69: 69<71, stack=[2,3,4]
i=5, t=72: 72>69, 弹出4, answer[4]=5-4=1
           72>71, 弹出3, answer[3]=5-3=2
           72<75, stack=[2,5]
i=6, t=76: 76>72, 弹出5, answer[5]=6-5=1
           76>75, 弹出2, answer[2]=6-2=4
           stack=[6]
i=7, t=73: 73<76, stack=[6,7]

代码

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 单调递减栈，存储索引

    for i, temp in enumerate(temperatures):
        # 当前温度 > 栈顶温度，弹出并计算
        while stack and temperatures[stack[-1]] < temp:
            prev_i = stack.pop()
            answer[prev_i] = i - prev_i

        stack.append(i)

    return answer

复杂度：时间 O(n)，空间 O(n)

例题 3：LC 84. 柱状图中最大的矩形（Hard）

题目：给定 n 个非负整数表示柱状图中各个柱子的高度，每个柱子彼此相邻且宽度为 1，求在该柱状图中能勾勒出的矩形的最大面积。

示例：

输入：heights = [2,1,5,6,2,3]
输出：10

思路：单调栈

关键观察：对于每个柱子，找到它左边和右边第一个比它矮的柱子，这之间的宽度就是它能扩展的最大宽度。

heights = [2, 1, 5, 6, 2, 3]

对于高度 5：
- 左边第一个比它矮的是 1（索引 1）
- 右边第一个比它矮的是 2（索引 4）
- 宽度 = 4 - 1 - 1 = 2
- 面积 = 5 * 2 = 10

对于高度 6：
- 左边第一个比它矮的是 5（索引 2）
- 右边第一个比它矮的是 2（索引 4）
- 宽度 = 4 - 2 - 1 = 1
- 面积 = 6 * 1 = 6

代码

def largestRectangleArea(heights: list[int]) -> int:
    # 添加哨兵，简化边界处理
    heights = [0] + heights + [0]
    stack = [0]  # 存储索引
    max_area = 0

    for i in range(1, len(heights)):
        # 当前高度 < 栈顶高度，计算栈顶的矩形面积
        while heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    return max_area

复杂度：时间 O(n)，空间 O(n)

例题 4：LC 42. 接雨水（单调栈法）

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算下雨之后能接多少雨水。

思路

用单调递减栈，横向计算每一层的雨水。

对于凹槽：[left, mid, right]
- left 是左边界
- right 是当前柱子
- mid 是底部

每一层的雨水 = (min(left, right) - mid) * (right - left - 1)

代码

def trap(height: list[int]) -> int:
    stack = []  # 单调递减栈，存储索引
    water = 0

    for i in range(len(height)):
        # 当前高度 > 栈顶高度，可以形成凹槽
        while stack and height[i] > height[stack[-1]]:
            mid = stack.pop()
            if not stack:
                break

            # 计算这一层的雨水
            left = stack[-1]
            h = min(height[left], height[i]) - height[mid]
            w = i - left - 1
            water += h * w

        stack.append(i)

    return water

复杂度：时间 O(n)，空间 O(n)

例题 5：LC 155. 最小栈

题目：设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

思路

用两个栈：一个存数据，一个存当前最小值。

代码

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # 最小栈存储当前最小值
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

复杂度：所有操作 O(1)

例题 6：LC 150. 逆波兰表达式求值

题目：给你一个字符串数组 tokens，表示一个逆波兰表达式，请计算该表达式的值。

示例：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：((2 + 1) * 3) = 9

代码

def evalRPN(tokens: list[str]) -> int:
    stack = []

    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))  # 向零取整
        else:
            stack.append(int(token))

    return stack[0]

复杂度：时间 O(n)，空间 O(n)

例题 7：LC 224. 基本计算器

题目：给你一个字符串表达式 s，请你实现一个基本计算器来计算并返回它的值。表达式包含 +、-、(、) 和空格。

思路

用栈处理括号，维护符号位。

代码

def calculate(s: str) -> int:
    stack = [1]  # 符号栈，初始为正
    sign = 1     # 当前符号
    result = 0
    i = 0

    while i < len(s):
        c = s[i]
        if c.isdigit():
            # 读取完整数字
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            result += sign * num
            continue
        elif c == '+':
            sign = stack[-1]
        elif c == '-':
            sign = -stack[-1]
        elif c == '(':
            stack.append(sign)
        elif c == ')':
            stack.pop()
        i += 1

    return result

复杂度：时间 O(n)，空间 O(n)

三、单调栈总结

什么是单调栈？

栈内元素保持单调递增或单调递减。

单调递减栈：从栈底到栈顶递减

  • 用于找下一个更大的元素
  • 栈顶是当前最小值

单调递增栈：从栈底到栈顶递增

  • 用于找下一个更小的元素
  • 栈顶是当前最大值

单调栈适用场景

场景栈类型
找下一个更大的元素单调递减栈
找下一个更小的元素单调递增栈
柱状图最大矩形单调递增栈
接雨水单调递减栈

单调栈模板

def monotone_stack(nums: list[int]) -> list[int]:
    """找下一个更大的元素"""
    n = len(nums)
    result = [-1] * n
    stack = []  # 单调递减栈

    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            result[stack.pop()] = nums[i]
        stack.append(i)

    return result

四、常见错误与陷阱

错误 1：忘记处理栈为空的情况

# 错误
while nums[i] > nums[stack[-1]]:  # stack 可能为空
    ...

# 正确
while stack and nums[i] > nums[stack[-1]]:
    ...

错误 2：单调栈方向搞反

# 找下一个更大的元素，用单调递减栈
while stack and nums[i] > nums[stack[-1]]:  # 正确

# 如果写成 <，就变成找更小的元素了
while stack and nums[i] < nums[stack[-1]]:  # 不同的用途

错误 3：柱状图问题忘记加哨兵

# 不加哨兵，需要额外处理剩余元素
heights = [2, 1, 5, 6, 2, 3]

# 加哨兵（首尾加 0），简化逻辑
heights = [0] + heights + [0]

五、复盘清单

触发信号

  • 括号匹配
  • 表达式求值
  • 需要记住最近的状态
  • 找下一个更大/更小的元素
  • 柱状图相关问题

边界条件

  • 空输入
  • 只有左括号/只有右括号
  • 单调栈处理完后剩余元素

常见错误

  • 忘记判空
  • 单调栈方向错误
  • 柱状图问题没加哨兵

六、题目清单

基础题

题号题目难度考点
20有效的括号Easy括号匹配
155最小栈Medium辅助栈
150逆波兰表达式求值Medium表达式求值
739每日温度Medium单调栈
496下一个更大元素 IEasy单调栈

进阶题

题号题目难度考点
84柱状图中最大的矩形Hard单调栈
42接雨水Hard单调栈
85最大矩形Hard单调栈+预处理
224基本计算器Hard栈
503下一个更大元素 IIMedium循环数组+单调栈