有效的括号

一、题目（LeetCode 20 · 简单 · Hot100）

给定一个只包含 '('、')'、'['、']'、'{'、'}' 的字符串 s，判断是否有效。左括号必须用相同类型的右括号闭合，且必须以正确的顺序闭合（嵌套、并列均合法）。

输入：s = "()[]{}"   输出：true
输入：s = "(]"       输出：false
输入：s = "([)]"     输出：false   // 交叉嵌套不合法
输入：s = "((("      输出：false   // 有左括号没被闭合

二、思路演进

2.1 朴素：反复消掉相邻的配对

不断把 "()"、"[]"、"{}" 三种子串替换成空串，直到替换不动：剩空串则合法。每轮全串扫描 O(n)，最多消 n/2 轮 → O(n²)，且 replace 每轮都产生新串对象，内存抖动大。能过但被追问复杂度就露怯。

2.2 关键洞察：最近出现的左括号最先被闭合——LIFO

观察合法串的消除顺序：任何时刻，下一个该匹配的右括号，对应的是最后那个还没闭合的左括号。"最后进、最先出"正是栈的定义：

• 遇左括号：压栈（登记一个待闭合的期待）；
• 遇右括号：必须与栈顶的左括号同类型，弹出；栈空或类型不符即非法；
• 扫描结束：栈必须为空（否则有没闭合的左括号）。

一个小技巧让代码更短：遇左括号时压入它期待的右括号。之后遇右括号直接与弹出值比对，省掉三对类型映射的判断分支。

三、复杂度分析

• 时间 O(n)：每个字符至多一次压栈、一次弹栈，均 O(1)——对比朴素法省掉的是"每轮全串重扫 + 串重建"。
• 空间 O(n)：最坏全是左括号（"(((("），全部入栈。

四、代码

package org.example;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_20 {

    public static void main(String[] args) {
        System.out.println(isValid("()[]{}"));  // true
        System.out.println(isValid("(]"));     // false：类型不匹配
        System.out.println(isValid("([)]"));   // false：交叉嵌套
        System.out.println(isValid("((("));    // false：栈没清空
        System.out.println(isValid(")("));     // false：右括号先来、栈空
    }

    public static boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;                  // 奇数长度必不合法，早退剪枝
        }
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(': stack.push(')'); break;   // 压入"期待的右括号"
                case '[': stack.push(']'); break;
                case '{': stack.push('}'); break;
                default:
                    // 来了右括号：栈空（无左可配）或与期待不符，都不合法
                    if (stack.isEmpty() || stack.pop() != c) {
                        return false;
                    }
            }
        }
        return stack.isEmpty();            // 还有左括号没被配对 -> false
    }

}

五、坑点

• 栈空时来右括号：")(" 首字符就是右括号，pop/peek 前不判空直接 EmptyStackException（或 ArrayDeque 抛 NPE）。这是本题最高频的运行时错误。
• 结束时栈非空要 false："(((" 不发生任何"不匹配"，漏掉末尾的 isEmpty 检查会误判 true。
• 比较方向：是"当前右括号"与"栈顶登记的期待"比，别写反成左右括号自比。
• 用 Deque 而不是遗留 Stack 类：Stack 继承 Vector、方法全同步，有无谓开销；ArrayDeque 是 JDK 推荐的栈实现（同族设计见 最小栈）。
• 奇数长度早退只是剪枝，逻辑上不是必需——删除也正确，留着是加分项。

六、变形追问

• 变体一（最长有效括号，LeetCode 32，Hot100）：从判合法变成求最长合法子串长度。栈改存下标而非字符，配对弹栈后用"栈顶剩余下标"计算长度，并放一个 -1 哨兵垫底。另有 DP 与双向计数两种 O(1) 空间解法，适合横向对比。
• 变体二（括号生成，LeetCode 22）：从"判定"翻转为"构造"。回溯生成所有合法组合，剪枝条件就是本题的合法性前缀。左括号未用完可放左，右括号数小于左括号数才可放右。

2026-10 新增（E 轨 · Hot100 第一批）。