LC20　有效的括号¶

简单通过率 45.8%python3核心代码模式栈样例通过牛客 AC栈字符串括号序列

讲解章节：栈

一句话

用栈记住尚未闭合的左括号，右括号只能和最近的那个配对。

解题思路¶

这题考什么¶

括号序列的合法性有两个条件，缺一不可：数量上左右配平，顺序上不能交叉。只统计计数是不够的——"([)]" 三种括号各一对，计数完全配平，却是非法的。

关键观察：任何一个右括号，只能与离它最近的那个还没闭合的左括号配对。 "([])" 里的 ']' 往左找，最近的未闭合左括号是 '['，配上； "([)]" 里的 ')' 往左找，最近的未闭合左括号是 '['，类型对不上，直接非法。「最近的未闭合的」正是后进先出（LIFO），这就是栈的定义，所以括号匹配是栈的标准入门题。见栈。

算法只有两条规则：遇左括号 -> 压栈（它成为新的「最近未闭合者」）；遇右括号 -> 栈顶必须是与之同类的左括号，弹掉表示这一对闭合，否则立即非法。扫完之后栈必须为空——栈里剩东西说明有左括号自始至终没被闭合。

实现上栈里直接压「这个左括号所期待的右括号」而不是左括号本身：比较时一次相等判断就够了，省掉一层「左右括号互查」的映射。

数据规模与复杂度¶

1 <= s.length <= 1e4，字符只可能是这六种括号。每个字符入栈出栈各至多一次，时间 O(n)，空间 O(n)—— 全是左括号（如 1e4 个连续的 '('）时栈会装下整个字符串。「反复删除相邻的 ()、[]、{} 直到不能删」也能判对，但每轮扫描只删掉一层，最坏要扫 n / 2 轮，退化成 O(n^2)，n = 1e4 时是 5e7 级的字符串重建，明显更差。

坑在哪¶

右括号来时栈可能是空的。字符串 "]" 或 ")()" 都会触发：不先判空就去取栈顶，Python 会抛 IndexError 而不是返回 false。
扫完必须检查栈空。"(((" 全程没有任何冲突，循环里一次都不会返回 false，只有结尾那句「栈空才算有效」能把它判掉。漏了这一步会把所有只有左括号的串判成有效。
类型必须逐对核对，不能只数个数。"([)]" 是这条的反例：左右括号数量、每种类型的数量都配平，但配对关系交叉，答案是 false。
长度为奇数的串一定非法，可以提前返回，但这只是常数优化，不能用它代替上面两条检查——"()(" 长度为奇数，"([)]" 长度却是偶数。
严格比对：答案是布尔值，唯一，没有多解。

样例复核¶

s = "([)]"，栈里存的是「期待的右括号」：

'(' -> 压入 ')'      栈 = [')']
'[' -> 压入 ']'      栈 = [')', ']']
')' -> 栈顶是 ']'，与 ')' 不符 -> 返回 false

s = "([])"：

'(' -> 栈 = [')']；'[' -> 栈 = [')', ']']；
']' -> 栈顶 ']' 相符，弹出，栈 = [')']；
')' -> 栈顶 ')' 相符，弹出，栈 = []；扫完栈空 -> true。

两个串的括号计数完全一样，结论却相反，正说明必须用栈而不是计数。

参考实现¶

solutions/leetcode/LC20/sol.py
from typing import List, Optional


class Solution:
    def isValid(self, s: str) -> bool:
        # 左括号 -> 它所期待的右括号。栈里直接存期待的右括号，
        # 比较时一次相等判断即可，不必再做一层左右互查
        pairs = {"(": ")", "[": "]", "{": "}"}
        # 栈顶 = 离当前位置最近的、尚未闭合的那个左括号所期待的右括号
        stack = []
        for ch in s:
            if ch in pairs:
                # 左括号：它成为新的「最近未闭合者」，压栈
                stack.append(pairs[ch])
            else:
                # 右括号：栈为空说明它前面根本没有待闭合的左括号（如 "]"），
                # 不先判空就取 stack[-1] 会抛 IndexError 而不是返回 false
                if not stack or stack.pop() != ch:
                    return False
        # 循环里只能发现「配错」，发现不了「没配完」——
        # "(((" 全程无冲突，靠这一句把它判掉
        return not stack

LC20 有效的括号¶