LeetCode 20：有效的括号（Valid Parentheses）题解

Valid Parentheses 是 LeetCode Hot 100 里面一道非常经典的栈题。

这道题通常被认为是学习栈结构时最基础、也最有代表性的题目之一。表面上看，它只是让我们判断一个字符串中的括号是否合法；但从本质上来说，这道题考察的是你能不能理解 “后进先出” 这种数据结构的使用场景。

很多人第一次看到这道题时，会觉得括号匹配好像不难，但真正开始写代码时，经常会遇到这些问题：

• 遇到右括号时应该怎么判断

• 什么时候返回 false

• 为什么最后还要判断栈是否为空

而你给出的这份 Java 代码，就是这道题最标准、最经典的写法。 本文就结合这段代码，系统地讲一下这道题的解法思路。

题目介绍

给定一个只包含下面几种字符的字符串 s：

• '('

• ')'

• '['

• ']'

• '{'

• '}'

判断字符串中的括号是否有效。

一个合法的括号字符串，需要满足两个条件：

1. 左括号必须用相同类型的右括号闭合

2. 左括号必须按照正确的顺序闭合

比如：

• "()" 是合法的

• "()[]{}" 是合法的

• "(]" 不合法

• "([)]" 不合法

• "{[]}" 合法

这道题要求我们返回一个布尔值：

• 合法返回 true

• 不合法返回 false

示例

示例 1

输入：s = "()"
输出：true

因为左括号 ( 正好被右括号 ) 正确匹配。

示例 2

输入：s = "()[]{}"
输出：true

这个字符串中有多组括号，但每一组都能正确配对，因此是合法的。

示例 3

输入：s = "(]"
输出：false

虽然有一个左括号和一个右括号，但类型不一致：

• 左边是 (

• 右边是 ]

因此不匹配。

示例 4

输入：s = "([)]"
输出：false

这个例子很典型。 虽然括号数量对得上，但顺序不对。

正确的匹配应该是“最后打开的括号，最先关闭”。 而这里的关闭顺序破坏了这个规则，所以不是合法字符串。

示例 5

输入：s = "{[]}"
输出：true

这个字符串的嵌套顺序是正确的：

• { 包着 [ ]

• [ ] 内部没有问题

• 最后 } 再闭合最外层

因此合法。

这道题为什么要用栈？

这道题最关键的一点，就是理解为什么括号匹配非常适合用栈来做。

我们来看括号匹配的本质：

• 遇到左括号时，说明有一个“未完成匹配”的括号，需要先记下来

• 遇到右括号时，要和“最近的那个还没匹配的左括号”进行配对

这个“最近的、尚未匹配的左括号”非常关键。

因为括号匹配满足一种典型规律：

后出现的左括号，要先被匹配。

比如：

{ [ ( ) ] }

这里最后出现的左括号是 (，所以它必须先和 ) 匹配； 然后才轮到 [ 和 ]； 最后才是 { 和 }。

这正好符合栈的特点：

后进先出（LIFO）

所以用栈来保存尚未匹配的左括号，是最自然、也最高效的做法。

核心思路

这道题的整体流程其实非常清晰：

1. 遍历字符串中的每个字符

2. 如果当前字符是左括号，就压入栈中

3. 如果当前字符是右括号，就从栈顶取出一个左括号进行匹配

4. 如果匹配失败，直接返回 false

5. 遍历结束后，如果栈为空，说明所有括号都成功匹配；否则说明还有多余左括号，返回 false

这就是这道题最标准的解法思路。

Java 代码

下面是你给出的代码，我这里保留原本逻辑，并加上注释方便理解：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
​
        for (char c : s.toCharArray()) {
            // 如果是左括号，直接入栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                // 如果是右括号，但此时栈为空，说明没有可匹配的左括号
                if (stack.isEmpty()) return false;
​
                char top = stack.pop();
​
                // 判断当前右括号和栈顶左括号是否匹配
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
​
        // 最后栈必须为空，才说明全部匹配成功
        return stack.isEmpty();
    }
}

代码拆解

虽然这段代码不长，但逻辑非常完整。 下面一步一步来看它到底在做什么。

1. 为什么要创建栈？

Stack<Character> stack = new Stack<>();

这个栈用来存放还没有被匹配掉的左括号。

比如遍历到下面这个字符串时：

"(["

我们会依次把：

• ( 压入栈

• [ 压入栈

此时栈顶是 [。

如果接下来遇到的是：

"]"

那么就应该优先和 [ 匹配，而不是和更早的 ( 匹配。

这就是为什么需要使用栈，而不是普通队列或者数组。

2. 为什么左括号直接入栈？

if (c == '(' || c == '[' || c == '{') {
    stack.push(c);
}

因为左括号本身还无法决定是否合法。 只有当未来某个右括号出现时，它才有机会完成匹配。

所以左括号出现时，我们只能先把它保存起来，等待之后的右括号来处理。

3. 为什么遇到右括号时要先判断栈空？

if (stack.isEmpty()) return false;

这一步特别重要。

因为如果当前字符是右括号，而栈里根本没有任何左括号，那么说明当前右括号没有对应的匹配对象。

比如：

s = ")"

或者：

s = "())"

当遍历到多出来的那个右括号时，栈已经空了。 这时候肯定不合法，直接返回 false。

如果不写这一步，后面执行 pop() 就会出错。

4. 为什么要弹出栈顶元素？

char top = stack.pop();

因为当前遇到一个右括号时，它应该匹配的是 最近压入栈、但还没有被匹配的左括号。

这个“最近”的概念，正是栈顶元素。

例如字符串：

"{[]}"

遍历过程大概是：

• { 入栈

• [ 入栈

• 遇到 ] 时，应该和 [ 匹配

• 遇到 } 时，应该和 { 匹配

所以每次都只需要看栈顶。

5. 为什么匹配失败就直接返回 false？

if ((c == ')' && top != '(') ||
    (c == ']' && top != '[') ||
    (c == '}' && top != '{')) {
    return false;
}

这是在判断当前右括号和弹出来的左括号是不是同一种类型。

如果不是，就说明括号类型不对应。

比如：

• 当前是 )

• 但栈顶弹出来的是 [

那显然不合法。

一旦发生这种情况，就不需要继续往后看了，因为整个字符串已经不可能是合法括号串，直接返回 false 即可。

6. 为什么最后还要判断一次 stack.isEmpty()？

return stack.isEmpty();

因为遍历结束之后，可能还有一些左括号没有被匹配。

比如：

s = "((("

遍历过程中不会出现任何类型冲突，也不会在中途返回 false。 但这个字符串显然不合法，因为所有左括号都没有对应的右括号。

这时候栈中还会残留元素，所以必须返回：

false

只有当栈最终为空时，才说明：

• 每个右括号都找到了正确的左括号

• 每个左括号也都被成功匹配掉了

这时才是真正的合法括号字符串。

手动模拟一遍

我们用一个经典样例来走一遍：

s = "{[]}"

第一步：读到 {

它是左括号，入栈：

stack = ['{']

第二步：读到 [

它也是左括号，继续入栈：

stack = ['{', '[']

第三步：读到 ]

它是右括号，所以弹出栈顶：

top = '['

判断：

• 当前是 ]

• 栈顶是 [

匹配成功。

此时栈变成：

stack = ['{']

第四步：读到 }

继续弹出栈顶：

top = '{'

判断：

• 当前是 }

• 栈顶是 {

匹配成功。

此时栈变成空：

stack = []

遍历结束后，栈为空，所以返回：

true

再看一个非法例子

我们再看：

s = "([)]"

第一步：读到 (

入栈：

stack = ['(']

第二步：读到 [

继续入栈：

stack = ['(', '[']

第三步：读到 )

弹出栈顶：

top = '['

但当前右括号是 )，它只能和 ( 匹配，不能和 [ 匹配。

所以此时直接返回：

false

这说明问题不只是“括号数量对不对”，而是“匹配顺序对不对”。

复杂度分析

时间复杂度

我们只遍历了一遍字符串，每个字符最多入栈或出栈一次，所以时间复杂度是：

O(n)

其中 n 是字符串长度。

空间复杂度

最坏情况下，字符串全是左括号，比如：

"((((((("

那么所有字符都会被压入栈中，因此空间复杂度是：

O(n)

这道题真正考察的是什么？

这道题表面上是在判断括号是否合法，但本质上是在考两个点：

第一，是否能识别栈的使用场景

只要题目中出现：

• 最近的

• 成对匹配

• 嵌套结构

• 后进先出

这些特征时，就要想到栈。

括号匹配就是最标准的一个例子。

第二，是否能处理边界情况

比如：

• 右括号出现时栈为空

• 类型不匹配

• 遍历结束后栈不为空

这些地方都是最容易出错的细节。

所以这道题虽然简单，但非常适合作为“栈”这个数据结构的入门题来练习。

还能怎么优化？

从逻辑上来说，这段代码已经非常标准了。

当然，很多题解还会写成另一种形式： 不是把左括号压栈，而是直接把“期待匹配的右括号”压栈。

例如：

• 遇到 (，就把 ) 压栈

• 遇到 [，就把 ] 压栈

• 遇到 {，就把 } 压栈

这样遇到右括号时，只需要判断它是否等于栈顶即可。

这种写法也很巧妙，但从理解角度来说，你现在这份代码已经足够清晰，而且更容易让初学者看懂。

总结

这道题的核心思路其实可以概括成一句话：

用栈保存尚未匹配的左括号，遇到右括号时就和栈顶进行匹配。

完整流程就是：

1. 遇到左括号，入栈

2. 遇到右括号，先判断栈是否为空

3. 再弹出栈顶，检查类型是否匹配

4. 如果中途出现不匹配，直接返回 false

5. 最后检查栈是否为空

如果栈为空，说明所有括号都刚好成对匹配；否则说明还有未闭合的左括号。

这是一道非常典型的栈基础题。 如果你正在系统刷 LeetCode，那么这题几乎一定要熟练掌握。因为它不仅出现频率高，而且能帮你建立对“栈”这种数据结构的直觉。

把这道题真正理解透之后，后面再遇到：

• 字符串解码

• 最长有效括号

• 表达式求值

• 单调栈相关问题

你都会更容易抓住核心。