有效的括号 图解题解

这道题真正在问什么

给一个只含 ()[]{} 六种字符的字符串，判断括号是否有效。有效要满足两条：每个左括号都被同类型的右括号闭合，且闭合顺序正确——后打开的括号必须先闭合，不能交叉。比如 "([]{()}[])" 有效，而 "([)]" 虽然左右数量都配平，却因为交叉闭合而无效。「顺序」这个约束，正是本题不能靠简单计数解决的原因。

为什么计数器不行，非要用栈

只有一种括号时，确实可以用计数器：遇 ( 加一、遇 ) 减一，过程中不许为负、最后归零即可。但三种括号混在一起，计数器只能保证每种数量配平，管不了嵌套顺序——"([)]" 三种计数全部平衡，却是非法的，因为 ) 来的时候最近还没闭合的是 [，类型对不上。

问题的本质是：一个右括号该配的对象，永远是「最近一个还没被闭合的左括号」。这是典型的后进先出关系——最晚进来的最先被处理——而后进先出正是栈这个数据结构的定义。可以说不是我们选择了栈，是题目的匹配规则长成了栈的形状。

扫描过程保持什么不变量

算法从左到右扫一遍：遇到左括号就压栈；遇到右括号就看栈顶——若栈为空，或栈顶左括号类型对不上，立即返回 false，否则弹出栈顶表示这一对成功闭合。全程保持的不变量是：栈里自底向上，恰好是「已经打开、还没闭合」的左括号，且越靠栈顶越新。

有了这条不变量，每一步的判断都有了依据：右括号来时只需要看栈顶一个元素，因为合法的闭合顺序规定它只能关最新打开的那个括号；栈顶配不上就绝无别的补救可能，直接判非法是安全的。

为什么最后还要检查栈是否为空

扫描中途不报错，不代表字符串有效。比如 "((("，全程没有任何配对失败，但三个左括号一直躺在栈里没人来关——左括号有剩余同样是非法的。所以最后一步必须检查栈空：栈空说明每个左括号都被恰好闭合过一次，返回 true；否则返回 false。

对称的另一头是「右括号多了」：比如 ")(" 开局就来右括号，此时栈是空的，没有任何左括号可配。这就是为什么处理右括号时要先判空再取栈顶——漏了判空，轻则逻辑错误，重则数组越界。

复杂度怎么算，还能怎么写得更顺

时间 O(n)：字符串扫一遍，每个字符至多压栈一次、弹栈一次，配对查表是 O(1)。空间 O(n)：最坏情况整串都是左括号，栈要装下全部 n 个字符。

实现上有个小技巧：与其建一张「右括号到左括号」的映射表去核对栈顶，也可以在遇到左括号时直接把它对应的右括号压进栈，之后遇到右括号只需和栈顶比是否相等，逻辑更直白。两种写法复杂度相同，选顺手的即可。

Python

def isValid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)        # 左括号压栈
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False         # 空栈/不匹配
            stack.pop()             # 配对成功弹栈
    return not stack                # 最后栈空才合法

Java

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (ch == '(') stack.push(')');
        else if (ch == '[') stack.push(']');
        else if (ch == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != ch)
            return false;           // 空栈/不匹配
    }
    return stack.isEmpty();         // 栈空才合法
}

C++

bool isValid(string s) {
    stack<char> st;
    for (char ch : s) {
        if (ch == '(') st.push(')');
        else if (ch == '[') st.push(']');
        else if (ch == '{') st.push('}');
        else if (st.empty() || st.top() != ch) return false;
        else st.pop();
    }
    return st.empty();              // 栈空才合法
}