有效的括号

问题拆解

给定一个只含 ()[]{} 的字符串，要判断括号是否正确闭合。合法有两个条件：类型要配对，顺序也要对。像 ([)] 三种括号数量都对，却因为交叉嵌套而非法。

我一开始想过“数一数每种括号左右是否相等”，但 ([)] 立刻推翻了这个想法——数量对不代表顺序对。真正的关键是：每遇到一个右括号，它必须闭合的是当前还没关闭的、离它最近的那个左括号。

“最近打开的必须最先关闭”，这句话本身就是栈的先进后出（LIFO）。

用栈匹配最近的左括号

把左括号一路压栈；遇到右括号时，栈顶就是“最近未闭合的左括号”，检查它们是否成对即可。我用一个字典把右括号映射到它期待的左括号，判断时更直接。

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

    for ch in s:
        if ch not in pairs:
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False

    return not stack

两个容易漏的边界：遇到右括号但栈是空的（没有左括号与之配对），直接判非法；遍历结束后栈必须为空，否则说明还有左括号没被关闭，比如 (((。

复杂度

指标	复杂度	原因
时间	O(n)	每个字符进出栈各一次
空间	O(n)	最坏情况全是左括号，全部压栈

可以迁移的模式

• 需要处理“嵌套”“配对”“就近匹配”的结构；
• 当前的决策只依赖“最近一次未完成的操作”；
• 逆序回收：后进来的先被处理掉。

看到“成对”“嵌套”“最近的一个”，先想想能不能用栈把“最近”这件事管起来。