有效的括号：从栈原理到Java实现，吃透这道Hot100面试题

Leetcode Hot100 的题目我基本都过了一遍，如果说哪道题最值得反复咀嚼，“有效的括号”一定排得进前五。题目本身不难，但它在面试里出现频率极高，而且往四周延伸能牵出至少五道变体题。这两年帮组里做技术面试，我至少有二十次让候选人现场手写这道题，能一次写对、还能把“为什么用栈”讲清楚的，其实不到一半。

这个现象很有意思。一道标着 Easy 的题，反而最能暴露出代码功底和算法理解的差距。所以这篇文章我不打算只贴一份能通过的 Java 代码，而是把这道题从题目设计、三种解法递进、复杂度分析、边界条件，到面试官会怎么追问、Hot100 里哪些题跟它是同一体系，全部摊开讲一遍。不管你是准备校招、社招，还是单纯想巩固栈的用法，这篇都值得收藏了慢慢看。

1. 题目到底在考什么：一道送分题背后的三个考点

1.1 题面与规则重读

先看题面：给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。有效字符串需要满足三个条件：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合，每个右括号都有一个对应的相同类型的左括号。

这里有一个容易被忽略的前提：字符串只包含这六种括号字符，没有字母、数字、空格。这个约束很重要，它意味着你不需要做任何字符过滤，直接进入匹配逻辑就行。新版的力扣题面把 s.length 限制在 1 <= s.length <= 10^4，但很多老版本题解里还会讨论空字符串的情况，按规则空串是有效的，写代码时稍微留意一下题面的差异即可。

拆开看，这三个条件其实对应三个层次的检查：

• 数量匹配：左右括号总数要相等。这个最基础，但只是必要条件，不是充分条件。
• 类型匹配：( 必须配 )，不能配 ]。
• 顺序匹配：([)] 这种字符串，数量对、类型也对，但顺序错，依然无效。

真正让这题有含金量的就是第三点：顺序匹配。如果你只统计左右括号数量，或者用简单的计数器，都处理不了 ([)] 这种交叉嵌套的情况。而“最近出现的左括号先被匹配”这个特性，恰好和栈的后进先出（LIFO）完全吻合。

1.2 为什么栈是这道题的标准答案

我一般喜欢用叠盘子来类比括号匹配：你把盘子一个一个往上叠，取的时候只能从最上面开始取。括号也是这样，{ [ ( ) ] } 这个嵌套里，( 是最后出现的左括号，所以它最先遇到自己的右括号 )，配对完成后消失，接着轮到 [ 配 ]，最后才是 { 配 }。这完全就是栈的操作过程：左括号入栈，遇到右括号时和栈顶元素比较，匹配则弹出，不匹配则直接判定无效。

从计算理论的角度看，括号匹配是一种非常典型的“最近匹配”问题，编译器做语法检查时也是这套逻辑。词法分析阶段把带括号的表达式拆成 token，语法分析阶段就需要维护一个符号栈，遇到右括号就从栈里弹出对应的左括号检查类型。所以这道题表面上是 LeetCode 题目，实际上是在模拟编译器的一个核心环节。

用栈解决的另一个原因是它的空间复杂度是可控的。最坏情况下字符串全是左括号，比如 ((((((...，栈深度等于字符串长度，空间复杂度 O(n)，这也是理论下界，因为你要记住所有未匹配的左括号，才能在未来某个时刻把它们配对。

1.3 Hot100 为什么把它放在这么靠前的位置

LeetCode Hot100 是很多人的刷题主线，而“有效的括号”能入选并且常年排在靠前位置，我觉得有三个原因。

第一，它是栈这种数据结构的“敲门砖”。栈本身不复杂，但很多初学者不知道栈到底有什么用，这道题给了栈一个再自然不过的应用场景。刷透这一题，后面再做 min stack、每日温度、柱状图最大矩形，思路会顺很多。

第二，它的实现可以同时考察多个 Java 基础点。比如你知道不知道 ArrayDeque 比 Stack 更适合当栈用？会不会用 Map 来建立括号映射？能不能说出遍历字符串时用 toCharArray() 和 charAt(i) 的区别？这些全是 Java 面试里的高频考点。一题牵连出这么多点，面试官当然爱用。

第三，它天然适合“一问多变”。面试官可以在写完这题后立刻追问“如果括号有优先级呢”“如果只允许一种括号呢”“如果要求返回第一个非法位置呢”，考察你的应变能力，这在后面的章节我会详细展开。

2. 三种 Java 实现：从暴力到性能最优的递进

2.1 解法一：字符串替换，能过但不建议

我第一次在 LeetCode 上看到这道题时，脑子里冒出来的第一个想法不是栈，而是字符串替换。既然成对的括号把中间清空后还是成对的括号，那我不断把 "()"、"[]"、"{}" 替换成空字符串，最后如果字符串变成空，不就说明所有括号都配对了吗？

代码写出来大概是这样：

java复制public boolean isValid(String s) {
    while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    }
    return s.isEmpty();
}

这个思路本身没问题，甚至在某些脚本语言里还挺优雅。但放到 Java 里，性能非常难看。replace 每次都要扫描整个字符串并创建新的字符串对象，时间复杂度在最坏情况下是 O(n^2)，比如字符串是 (((((((...))))) 这种深嵌套结构，每一层括号匹配都要完整扫描一次字符串。LeetCode 的测试用例不会让这个做法超时，毕竟 s.length 只有 10^4，但面试的时候你这么写，面试官大概率会皱眉头。

我建议把它留作“思维热身”就好，公开场合别用。它唯一的价值是帮助你理解“括号匹配是一个不断消去成对子串的过程”，这个直觉对后面理解栈有帮助。

2.2 解法二：哈希表加双端队列，面试的标准答案

正儿八经的解法是用栈。Java 里实现栈有几种选择，我推荐的写法是 Deque<Character> stack = new ArrayDeque<>()，配合一个 HashMap 来存储右括号到左括号的映射。为什么不直接 Stack<Character>？因为官方 Stack 类继承了 Vector，所有方法都带同步锁，性能有额外开销，而且它现在基本算历史遗留类，Java 官方文档也更推荐用 Deque 接口。面试时主动用 ArrayDeque，本身就是一个加分项。

完整代码：

java复制class Solution {
    private static final Map<Character, Character> PAIRS = new HashMap<>();

    static {
        PAIRS.put(')', '(');
        PAIRS.put(']', '[');
        PAIRS.put('}', '{');
    }

    public boolean isValid(String s) {
        // 长度为奇数，不可能完全配对，直接返回 false
        if ((s.length() & 1) == 1) {
            return false;
        }

        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // 如果是右括号，检查栈顶是否匹配
            if (PAIRS.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != PAIRS.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                // 左括号入栈
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}

整个流程分三段理解。第一段是奇数长度剪枝：一对括号消耗两个字符，长度为奇数的字符串一定不合法，直接返回，省一次完整的遍历。第二段是遍历：遇到左括号就压栈；遇到右括号，先看栈空不空，栈空了说明没有可配对的左括号，返回 false，栈不空则看栈顶是不是对应的左括号，不是则类型不匹配，也返回 false。第三段是收尾：遍历完所有字符后，栈必须是空的，否则说明还有没配完的左括号，比如 "((()" 这种。

这个写法有个细节我觉得值得多说一句：为什么 HashMap 只放右括号到左括号的映射，而不是左括号到右括号？因为遍历字符串时，我们处理的分支是“遇到右括号才需要查映射”。如果存左括号到右括号的映射，遇到右括号时你还得反向遍历 map 才能找到对应的左括号，非常绕。顺着执行逻辑来设计映射方向，代码会自然很多。

2.3 解法三：用 char 数组手写栈，性能党的选择

如果你想在 LeetCode 上把这道题跑进极致的性能区间，还有一个招：不用任何现成的栈容器，直接用 char[] 数组自己维护一个栈指针。

java复制public boolean isValid(String s) {
    if ((s.length() & 1) == 1) {
        return false;
    }

    char[] stack = new char[s.length()];
    int top = -1;

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack[++top] = c;
        } else {
            if (top == -1) {
                return false;
            }
            char left = stack[top];
            if ((c == ')' && left == '(')
                    || (c == ']' && left == '[')
                    || (c == '}' && left == '{')) {
                top--;
            } else {
                return false;
            }
        }
    }

    return top == -1;
}

核心思路和栈版本完全一致，只是把“栈”换成了数组加指针。top 初始化为 -1，表示栈为空，压入一个元素就先 ++top 再赋值，弹出则 top--。数组长度直接取 s.length()，因为栈里的元素数量永远不可能超过字符串长度，这是最安全的容量。

这个版本的性能优势很明显：省去 ArrayDeque 内部对象数组的动态扩容，省去 HashMap 的哈希计算，只需要一个 int 指针和一次字符数组遍历。实测在 LeetCode 上一般能击败 90% 以上的提交，内存也能压到很低。缺点是代码可读性稍差，匹配逻辑要写三个判断条件。所以我一般建议面试时先把解法二写出来，如果面试官问“还能不能优化”，再给他展示这版，顺便讲清楚优化点在哪里。这比一上来就写数组版本要稳妥，因为面试官可能更看重代码的清晰度。

3. 复杂度分析和边界条件实测

3.1 时间复杂度与空间复杂度该怎么算

这道题的时间复杂度是 O(n)，其中 n 是字符串长度。因为无论哪种栈实现，每个字符都只被访问一次，入栈或出栈的操作都是 O(1)。你可能会想，HashMap 的 containsKey 不是也要算时间吗？是的，但哈希表的查找平均是 O(1)，所以整体仍是线性时间。理论上，任何检查括号匹配的算法都必须至少读一遍字符串，所以 O(n) 已经是这道题的最优时间复杂度。

空间复杂度需要分情况。使用 HashMap 的版本，映射表是固定大小的（只有三个键值对），可以认为是 O(1) 的辅助空间。主要变量是栈本身，最坏情况下字符串全是左括号，比如 "(((((((..."，所有字符都进栈，栈深度等于 n，所以空间复杂度是 O(n)。平均情况下要好一些，但分析复杂度时必须按最坏情况来算。

解法三的数组栈空间复杂度同样是 O(n)，但它不涉及动态扩容，实际占用的内存更小，因为 ArrayDeque 底层数组的容量往往是 2 的幂次，可能出现容量比实际元素多的情况。如果你在面试中能把这一层也说出来，会显得你确实思考过实现细节。

3.2 六个容易踩坑的边界用例

我自己刷题和面试别人时，发现很多人代码逻辑没问题，但栽在一些边界用例上。列一个速查表，建议写代码前先在心里过一遍这些场景：

我见过不少候选人能写出 "([)]" 返回 false，因为他们的代码在遇到 ] 时会把 [ 弹出来比较，发现栈顶是 (，于是返回 false。但也有人只统计数量，不记录类型，结果 "([)]" 就漏过去了。所以面试时我特别喜欢用 "([)]" 作为反例来追问，如果你自己没测过这个用例，现场很容易翻车。

另一个高频坑是忘记收尾检查栈是否为空。比如输入是 "(()"，遍历过程中没有出现任何匹配失败，但最后栈里还剩一个 (，这时候必须返回 false。如果你只写了循环里的匹配逻辑，没写最后的 stack.isEmpty()，这道题就直接错了。这个 bug 极其隐蔽，因为示例用例不会暴露它。

3.3 一个容易被忽略的 Java 细节

用 ArrayDeque 存字符时，peek() 返回的是 Character 对象，而 PAIRS.get(c) 返回的也是 Character 对象。比较的时候要用 != 还是 equals？这里有个 Java 的基本功陷阱：Character 是包装类型，用 == 比较的是对象引用。但别担心，字符常量在 Java 里大部分会被缓存到常量池，Character 的缓存范围是 0 到 127，括号的 ASCII 码都在这个范围内，所以用 == 实际也能正确工作。

不过我不建议依赖这种缓存机制写代码。更稳妥、可读性更好的方式有两种：一是直接比较 char 基本类型，把栈声明成 Deque<Character> 后 peek() 返回的是 Character，会自动拆箱成 char；二是用 equals 方法。我给出的代码里 stack.peek() != PAIRS.get(c) 能正常工作的原因是自动拆箱，但如果你换成自定义对象或者字符串，这里就会踩坑。面试时如果能主动提一句“这里用 char 基本类型比较，所以可以直接用 !=”，会显得你对 Java 的类型系统很熟。

顺便说一个很多 Java 新手会写错的点：不要把 charAt(i) 和 toCharArray() 混着乱用。两种遍历方式时间复杂度相同，但 toCharArray() 会额外创建一个字符数组，内存开销略高；charAt(i) 不会。对这道题差别微乎其微，不过在意细节的话，用 charAt(i) 配合 for 循环是一种更省内存的写法。我代码里用 toCharArray() 主要是为了简洁，两种都行，面试时别因为这种细节卡住就好。

4. 面试官视角：这道题还能怎么追问

4.1 五个高频追问及答法

写完这道题之后，面试官一般不会立刻放你走。他手里捏着好几个追问按钮，每一个都对应不同的知识点。

追问一：为什么这个题必须用栈？答：因为括号匹配遵循“最近匹配”原则，最后出现的左括号最先被配对，这就是后进先出。如果只用计数器，你只能判断数量是否相等，无法判断顺序是否正确，比如 "([)]" 数量全对但仍不合法。

追问二：空间复杂度能不能降到 O(1)？答：如果括号类型只有一种，比如只有 ()，确实可以退化成一个计数器，遇到左括号加一，遇到右括号减一，中途不得为负，最后等于零。但本题有六种括号，必须记录未匹配括号的类型和顺序，所以 O(n) 空间是必需的，这也是下界。

追问三：如果是流式输入怎么办？每次只能读取一个字符？答：栈结构天然适合流式处理，因为不需要回头扫描，每来一个字符就决定下一步动作。流式场景下栈的深度就是当前未匹配左括号的数量，内存压力取决于括号嵌套的最大深度，而不是总长度。

追问四：如果括号类型不止三种，比如还要支持 < 和 > 呢？答：扩展映射表即可，但需要注意 < 和 > 在 XML/HTML 语境下还有特殊含义。这类开放性问题考察的是你能否把方案抽象成“括号类型可配置”的设计，而不是写死三个 if。

追问五：如果我想知道第一个非法字符的位置，该怎么改？答：遍历时如果发现栈空但遇到了右括号，或者栈顶不匹配，就返回当前下标。这种变体在很多在线编辑器、IDE 的语法检查功能里就是真实需求，难度不大但很实用。

这些追问其实指向了同一个能力：能不能从一道题里抽象出通用的解决方案。这也是 LeetCode Hot100 的价值所在，它选的题目都不是孤立的，而是某个知识点的代表。

4.2 Hot100 里同体系题目横向对比

“有效的括号”在 Hot100 里不是孤岛。以它为核心，可以辐射出好几道栈相关题目，我按考察方向整理成了表格：

我刷题时的经验是：把“有效的括号”做透之后，上面的题可以连着刷，因为它们的核心都是“用栈维护一个待匹配/待处理的序列”。尤其是 1249，它几乎就是本题的工程化版本，要求你不仅判断合法性，还要输出删除哪些字符后合法，非常贴近真实开发里“清洗脏数据”的需求。

4.3 关于热词里那些 Java 相关帖子的碎碎念

我注意到这个标题相关的搜索词里，混着很多“java八股文”“java面试题”“java基础”之类的关键词。这其实反映了目前 Java 学习者的普遍焦虑：Java 岗位面试越来越卷，八股文满天飞，反而把基本功挤到了角落。

但你细想就会发现，如果能把“有效的括号”的来龙去脉吃透，很多围绕它的“八股”你都能顺手答出来。比如：

• 你知道 Stack 和 ArrayDeque 的区别吗？答：Stack 继承自 Vector，方法带锁，ArrayDeque 是双端队列，做栈用性能更好。
• 你知道哈希表的查找为什么平均 O(1) 吗？答：哈希函数把 key 映射到桶，链表/红黑树解决冲突。
• 你知道字符在 Java 里的存储方式吗？答：char 是两个字节的 UTF-16 code unit，括号的码点都在 BMP 范围内。

这些全是 Java 基础，但都能通过这一道题串起来。所以我一直觉得，与其背几十篇八股文，不如把 Hot100 里的经典题一个个“榨干”来得实在。

5. 实操心得：从 AC 到手写不卡壳的练习方法

5.1 我第一次做这题时踩的坑

我最初刷这道题的时候，犯过一个特别低级的错误：把 PAIRS 映射表定义成了 Map<Character, Character> pairs = Map.of('(', ')', '[', ']', '{', '}')，然后遍历到右括号时去 pairs.containsValue(c)，再反向找 key。这个方法能跑，但代码丑到不行，每次匹配都要遍历一遍 map，时间复杂度直接变成 O(n × 括号类型数)。

后来看了官方题解才明白，映射表的方向性设计不是随手写的，而是根据“遍历到右括号时需要查栈顶期望的左括号”这个动作来定的。存 右 -> 左，遇到右括号查一次映射，拿到期望的左括号，跟栈顶一比就完事。这就是为什么我说“顺着执行逻辑来设计数据结构”，代码会自然好写很多。

另外一个小坑是括号类型多的时候，匹配条件容易写错。比如有人会写 if (c == ')' && top == '(')，只判断了右括号和左括号的配对关系，却忘了如果栈顶是 [，这条判断不成立就会走 else 返回 false，逻辑上反而对了。但如果把所有左括号的判断都混在一个条件里，很容易出现“匹配上了却忘了 pop”的漏网之鱼。我的建议是匹配逻辑不要过度精简，宁可多写几个条件，也要保证每种情况都被覆盖。

5.2 可以照抄的刷题流程

如果你是一个准备面试的 Java 开发者，我建议用下面这个流程吃透这道题：

第一步：限时 10 分钟，不看题解，独立写出解法。这一步是逼自己回忆栈的用法，不要一上来就查资料。

第二步：对照官方题解和我的解法，找出差异。重点关注三个点：栈容器选什么、映射表方向怎么设计、边界条件处理是否完整。

第三步：隔 24 小时，在不看任何参考的情况下重新手写一遍。写完后用 "([)]"、"(()"、")(" 这几个用例自测。这个“隔夜默写”是我刷题最推荐的检验方式，能默写出来才算真会。

第四步：顺手把 1249 移除无效的括号 和 921 使括号有效的最少添加 做一遍。这两题做完了，你对括号匹配这个知识点的理解会是别人的好几倍。

第五步：再把数组栈优化版本写一遍，体会性能差异。面试如果时间充裕，可以主动展示两个版本，并告诉面试官“如果追求代码可读性我会选哈希表加栈，如果追求极致性能我会选数组栈，它们的时间复杂度都是 O(n)”。

这套流程看着简单，但很多人只做到第一步就停了。刷题最忌讳“看懂了”而不是“写会了”，隔夜默写能有效避开这个陷阱。

5.3 最后分享一点个人经验

这道题我前后应该写了快二十遍。每次准备面试，我都要重新默写一遍，不是为了背答案，而是为了让自己保持对栈操作的肌肉记忆。后来带新人，我也一直推荐“一道题反复榨干”的刷法，而不是一天刷十道新题。

有个小技巧你可能会喜欢：面试写代码时，先主动说一遍你的测试用例清单，比如“我会先用 "()" 验证基本匹配，用 "([)]" 验证顺序，用 "(" 验证栈空情况，用 "(()" 验证最终栈非空的情况”。这句话一说出口，面试官大概率会点头，因为这表明你考虑过边界，而很多人正是死在边界上的。代码写完后再跑一遍自测用例，基本上这一题就稳了。

LeetCode Hot100 是个好东西，但它不是用来“刷完”的，而是用来“刷透”的。“有效的括号”作为一个入门的栈题目，值得你花一晚上把它从里到外研究明白。等你真正吃透了它，再看栈相关的其他题目，眼光会完全不一样。