开发者日记

外观

一文搞懂最小栈与括号匹配：辅助栈设计与对称校验 ​

为什么栈类面试题总在考这两类 ​

栈（stack）是一种「后进先出」（LIFO）的线性结构，只允许在栈顶做插入和弹出。正因为操作受限，它特别适合处理两类问题：一类是需要随时记录历史极值，典型代表是最小栈；另一类是需要做嵌套与对称校验，典型代表是括号匹配。

这两道题几乎是数据结构面试的「必考题」，原因有三：代码量小、边界条件多、能快速考察候选人对辅助结构的设计能力。很多人能写出大致逻辑，却在重复压栈、空栈弹出、多种括号配对等细节上翻车。

本文从问题背景出发，对比不同设计方案，给出可直接运行的代码，并总结实战中的避坑要点。

问题一：最小栈的辅助栈设计 ​

题目描述 ​

设计一个栈，支持以下操作，且 getMin 必须在 O(1) 时间内完成：

  • push(x)：元素入栈
  • pop()：删除栈顶元素
  • top()：获取栈顶元素
  • getMin()：获取栈中最小元素

方案对比 ​

最直观的想法是每次 getMin 都遍历整个栈，但这需要 O(n) 时间，不满足要求。第二种方案是用一个变量记录最小值，可一旦最小值被弹出，就无法知道「次小值」是谁。

真正稳妥的做法是引入辅助栈：主栈正常存数据，辅助栈同步维护「每个状态下的最小值」。下面这张图展示了入栈过程中两个栈的对应关系。

主栈 data辅助栈 min_stack3（栈底）31141（重复压入）2（栈顶）1同步维护当前最小值

可运行代码：双栈同步 ​

python
class MinStack:
    def __init__(self):
        self.data = []          # 主栈：存放所有元素
        self.min_stack = []     # 辅助栈：存放每个状态的最小值

    def push(self, val: int) -> None:
        self.data.append(val)
        # 关键：当 val 小于等于当前最小值时也要压栈，
        # 使用 <= 而非 <，保证重复最小值弹出后仍有记录
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if not self.data:
            return
        val = self.data.pop()
        # 若弹出的值等于辅助栈栈顶，则辅助栈同步弹出
        if self.min_stack and val == self.min_stack[-1]:
            self.min_stack.pop()

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

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


# 测试用例
stack = MinStack()
stack.push(3)
stack.push(1)
stack.push(4)
stack.push(2)
print(stack.getMin())  # 1
stack.pop()            # 弹出 2
print(stack.getMin())  # 1

复杂度分析 ​

  • 时间复杂度：push、pop、top、getMin 均为 O(1)，每个元素至多入栈、出栈一次。
  • 空间复杂度：O(n)。最坏情况下（元素严格递减），辅助栈与主栈等长。

还有一种「栈中存差值」的单栈写法，能节省辅助栈空间，但涉及溢出和符号还原，工程可读性较差，面试中优先推荐双栈方案。

问题二：括号匹配的对称校验套路 ​

题目描述 ​

给定一个只包含 ()、{}、[] 的字符串，判断字符串中的括号是否有效。有效需满足：左括号必须用相同类型的右括号闭合，且闭合顺序正确，例如 ()[]{} 有效，(] 与 ([)] 无效。

核心思路 ​

括号的嵌套本质上就是「后出现的左括号先被闭合」，这与栈的 LIFO 特性完全吻合。套路固定为三步：

  1. 遇到左括号，将其对应的右括号压入栈；
  2. 遇到右括号，检查它是否与栈顶相等，相等则弹出，否则立即判定无效；
  3. 遍历结束后，栈必须为空，否则说明存在未闭合的左括号。
读取字符是左括号？压入对应右括号是右括号与栈顶比较栈空或不匹配返回 False匹配则弹栈继续遍历遍历结束栈为空？空则 True，否则 False

可运行代码：哈希表加栈 ​

python
def is_valid(s: str) -> bool:
    stack = []
    # 左括号到右括号的映射，压栈时直接存「期待出现的右括号」
    pairs = {'(': ')', '[': ']', '{': '}'}

    for ch in s:
        if ch in pairs:                 # 左括号：压入期待的右括号
            stack.append(pairs[ch])
        else:                           # 右括号：必须与栈顶相等
            # 注意先判断栈空，否则直接取 [-1] 会抛 IndexError
            if not stack or stack[-1] != ch:
                return False
            stack.pop()

    return len(stack) == 0  # 栈空才代表全部闭合


# 测试用例
print(is_valid("()[]{}"))   # True
print(is_valid("(]"))       # False
print(is_valid("([)]"))     # False
print(is_valid("{[]}"))     # True
print(is_valid("("))         # False（存在未闭合左括号）

复杂度分析 ​

  • 时间复杂度：O(n)，只需扫描字符串一次，每个字符的栈操作都是 O(1)。
  • 空间复杂度：O(n)，最坏情况（全是左括号）栈中保存 n 个期待字符。

进阶：带通配符或求最长有效括号 ​

掌握基础套路后，常见变种都建立在栈之上：求「最长有效括号子串」时，可在栈底压入一个基准下标 -1，遇到右括号弹出后用当前下标减去新栈顶来计算长度；表达式求值则用「双栈」分别存数字和运算符。理解「栈保存尚未完成的状态」这一本质，变种就不再是死记硬背。

避坑总结：高频错误与修正方法 ​

  1. 最小栈用 < 而非 <= 导致重复最小值丢失。 现象：连续压入两个 1，弹出一个后 getMin 报错或返回错误值。原因是相同最小值只记录了一次。修正：入栈判断写成 val <= self.min_stack[-1]，让每个最小值在辅助栈中都有对应记录，弹出时才能一一同步。

  2. 空栈上直接取栈顶或弹出。 现象：执行 pop()、top()、getMin() 时抛出 IndexError: list index out of range。括号匹配中字符串以右括号开头（如 ")("）也会触发。修正：取值前先用 if not stack 判空，题目未保证非空时尤其不能省略。

  3. 括号匹配只比较「是否成对」而忽略「类型」和「顺序」。 现象：(] 或 ([)] 被错误判为有效。修正：必须校验右括号与栈顶严格相等，而不是分别统计左右括号数量；计数法只能处理单一括号类型，多种括号嵌套必须用栈。

  4. 遍历结束忘记检查栈是否为空。 现象："(" 这类左括号未闭合的字符串被误判为有效。修正：返回条件写成 len(stack) == 0，确保所有压入的期待括号都被消费。

  5. 辅助栈与主栈弹出不同步。 现象：主栈弹出了最小值，辅助栈却没有弹出，getMin 返回已经不存在的元素。修正：pop 中先取出被弹值，当其等于辅助栈栈顶时同步弹出，保持两个栈的状态一致。

栈的题目代码通常不长，面试官真正看重的是你能否说清「为什么用栈」「辅助结构记录了什么状态」以及边界条件是否完备。把最小栈的「同步记录历史极值」和括号匹配的「栈顶即最近期待」这两个套路吃透，同类问题便能举一反三。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

本文来自开发者日记（devdiary.cn）· 记录开发者实战笔记与免费在线工具箱

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。