跳到正文
第 20 题简单

有效的括号

Valid Parentheses

给定只含三种括号的字符串，判断每个右括号是否都按正确的类型和顺序闭合了对应的左括号。

在力扣中练习

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

 

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

解题思路

主解法

栈 · 配对表

右括号只跟最近一个没配对的左括号配

只数左右括号数量不够：[(]) 数量相等，嵌套顺序却错了。需要保存尚未闭合的左括号，并且每个右括号只能与最近的那一个匹配，这正是栈的后进先出。

自拟主例 s = "{[()]}[(])" 长度为偶数，前半段能正常配完，后半段仍然会出错。左括号入栈；读到右括号时，先确认栈非空，再检查栈顶类型。

分步图解

读到左括号 {，压入栈顶。

s
0
1
2
3
4
5
6
7
8
9
{
[
(
)
]
}
[
(
]
)
c
尚未配对的左括号后进先出
{↓ 入栈
  1. {← top
栈底
1 / 4
右括号只检查当前栈顶，配对成功才弹出。

匹配成功才弹出。主例读到后半段的 ] 时需要 [，栈顶却是 (，因此立即返回 false。

分步图解

读到左括号 [，压入栈顶。

s
0
1
2
3
4
5
6
7
8
9
{
[
(
)
]
}
[
(
]
)
c
尚未配对的左括号后进先出
[↓ 入栈
  1. [← top
栈底
1 / 3
正确前缀不能保证整串正确，后半段的错配立即失败。

若一直没有错配，最后还必须检查栈空；否则说明左括号有剩余。奇数长度只是提前失败的条件，偶数长度并不保证合法。

时间 O(n)空间 O(n)

易错点

  • 先写 st.top() 再判空：空栈调用 top() 是未定义行为，顺序不能反。
  • 循环结束直接 return true，漏掉栈非空的情况 —— "((" 会被误判为有效。
  • 用「左右括号数量相等」代替配对："([)]" 数量相等但顺序错误。
对照解法

栈 · 存期望值

压栈时就把「该来的右括号」写好，比对更直接

同样是 O(n) 的正确栈解法，栈中保存期待的右括号，表达方式不同，判断标准相同。

同一个栈，换一种存法：压进去的不是左括号，而是「它期待收到的右括号」。

这样判断时就多余的操作都没有了：来一个右括号 c，只要 expect.top() == c 就配对成功。左括号的三种情况在入栈时一次写清楚，后面不用再查表，也不需要 unordered_map。内存上更省，理解上也更贴近栈的本质：栈里堆着的是一串「待办事项」，每条写着「接下来必须出现什么」。

不变式仍然是那句：栈里从栈底到栈顶，正好是当前所有尚未闭合的括号，按出现的先后排列。所以右括号只能匹配栈顶这条待办。

两种写法复杂度一样，选哪种看团队习惯；第一种的 match 表在括号种类很多时更好扩展，第二种在只有三种括号时更紧凑。

  1. 1遇到 ( 就压入 )，遇到 [ 就压入 ]，遇到 { 就压入 }。
  2. 2遇到右括号时，与栈顶比较。
  3. 3栈空或不相等返回 false，相等则弹出。
  4. 4全部字符处理完后，栈空即有效。
时间 O(n)空间 O(n)

易错点

  • 遇到右括号时忘记先判空，空栈取 top() 崩溃。
  • 压栈时写错成左括号本身（遇到 ( 却压入 (），右括号一来就永远对不上，答案会全部变成 false。

代码与演示

主解法配有图解；对照解法用于比较思路、复杂度或实现方式。

演示输入s = "{[()]}[(])"

先检查长度；当前长度为偶数，还需要逐个检查嵌套顺序。

s
0
1
2
3
4
5
6
7
8
9
{
[
(
)
]
}
[
(
]
)
尚未配对的左括号后进先出
从栈顶进入与离开
    空栈
    栈底
    1 / 10
    查看 C++ 代码

    延伸阅读

    • 栈擅长处理「最近一次还没做完的事」：字符串解码（394）、简化路径（71）、有效的括号字符串（678）都是这个模式。
    • 只有一种括号时，栈可以退化成计数器，空间 O(1)；一旦有多种类型，就必须记住类型和顺序。
    • 「最长有效括号」（32）是这套逻辑的加强版，用栈存下标而不是字符。