Valid Parentheses 是 Grind 75 中非常经典的一道题。

题目本身不算难，却特别适合用来理解 Stack，也就是“栈”。

很多人背得出这句话：

遇到左括号就入栈，遇到右括号就出栈。

但真正写代码时，还是容易卡住：

• 为什么一定要用 Stack？
• 右括号出现时，应该和谁比较？
• 什么情况下可以出栈？
• 字符串扫描结束后，为什么还要检查 Stack？

下面用流程图和一个完整例子，把整个过程拆开讲清楚。

一、题目要求

给定一个只包含以下六种字符的字符串：

( ) [ ] { }

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

有效字符串需要满足三个条件：

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

示例

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

二、为什么这道题适合使用 Stack？

先看一个有效字符串：

([{}])

左括号出现的顺序是：

( → [ → {

右括号关闭的顺序却是：

} → ] → )

也就是说：

最后出现的左括号，最先被关闭。

具体配对关系是：

(  [  {  }  ] )
      └──┘
   └────────┘
└─────────────┘

最里面的 { 最先遇到对应的 }。

然后是 [ 和 ]。

最外面的 ( 最后才和 ) 配对。

这正好符合 Stack 的特点：

Last In, First Out
后进先出

可以把 Stack 想成一摞盘子。

最后放上去的盘子
必须最先拿走

括号匹配也是同样的道理：

最近出现、还没有关闭的左括号
必须最先被右括号关闭

三、Stack 解法的核心规则

从左到右扫描字符串。

遇到左括号

下面三种字符都是左括号：

(
[
{

将它放入 Stack。

这个动作叫作：

入栈 Push

遇到右括号

下面三种字符都是右括号：

)
]
}

这时不能直接出栈，而是要先检查两件事。

第一件事：Stack 是否为空？

如果 Stack 是空的，说明当前右括号前面没有可以和它配对的左括号。

例如：

")"

第一个字符就是右括号，显然无效。

第二件事：栈顶括号是否匹配？

右括号只能和对应类型的左括号配对：

) 对应 (
] 对应 [
} 对应 {

例如当前字符是 ]，Stack 顶部必须是 [。

匹配成功，才能把栈顶左括号移除。

这个动作叫作：

出栈 Pop

如果类型不同，立即返回 false。

四、完整算法流程图

┌─────────────────────┐
│ 开始执行 │
└──────────┬──────────┘
│
▼
┌─────────────────────┐
│ 创建一个空的 Stack │
└──────────┬──────────┘
│
▼
┌─────────────────────┐
│ 从左到右读取一个字符 │
└──────────┬──────────┘
│
▼
┌───────────────┐
│ 字符是否存在？ │
└───────┬───────┘
是 │ 否
│
┌───────▼────────┐
│ 是否为左括号？ │
└───────┬────────┘
是 │ 否
│
┌───────▼────────┐
│ 将左括号压入栈中 │
│ Stack.push() │
└───────┬────────┘
│
└───────────────┐
│
▼
继续读取下一个字符

遇到右括号时，流程继续如下：

当前字符是右括号
│
▼
┌────────────────┐
│ Stack 是否为空？│
└───────┬────────┘
是 │ 否
│
┌───────────▼───────┐
│ 直接返回 false │
│ 没有左括号可匹配 │
└───────────────────┘

否
│
▼
┌───────────────────────┐
│ 栈顶左括号是否与它匹配？│
└───────────┬───────────┘
否 │ 是
│
┌───────────▼───────┐
│ 直接返回 false │
│ 括号类型不匹配 │
└───────────────────┘

是
│
▼
┌────────────────────┐
│ 弹出 Stack 栈顶元素│
│ Stack.pop() │
└──────────┬─────────┘
│
▼
继续读取下一个字符

当所有字符都扫描结束后：

┌─────────────────────┐
│ 所有字符已经扫描完毕 │
└──────────┬──────────┘
│
▼
┌─────────────────┐
│ Stack 是否为空？ │
└────────┬────────┘
是 │ 否
│
┌───────────▼──────┐ ┌────────────────┐
│ 返回 true │ │ 返回 false │
│ 所有括号均已配对 │ │ 仍有左括号未关闭│
└──────────────────┘ └────────────────┘

把整个流程压缩成一句话就是：

左括号入栈
右括号检查栈顶
匹配成功就出栈
最后栈为空才有效

五、完整图解：([{}]) 如何匹配成功？

字符串：

( [ { } ] )

字符索引：

0 1 2 3 4 5

我们从左到右逐个读取。

约定：

Stack 最右边是栈顶

第 1 步：读取 (

当前字符：

(

这是一个左括号，所以将它压入 Stack。

读取前：

Stack: [ ]


读取字符：

( [ { } ] )
↑


执行入栈：

stack.push("(")


读取后：

Stack: [ ( ]
↑
栈顶

当前状态：

已经读取：(
还未读取：[{}])

Stack: [ ( ]

第 2 步：读取 [

当前字符是左方括号 [。

继续入栈。

读取字符：

( [ { } ] )
↑


入栈前：

Stack: [ ( ]


执行：

stack.push("[")


入栈后：

Stack: [ ( , [ ]
↑
栈顶

当前状态：

已经读取：([
还未读取：{}])

Stack: [ ( , [ ]

第 3 步：读取 {

当前字符是左大括号 {。

继续入栈。

读取字符：

( [ { } ] )
↑


入栈前：

Stack: [ ( , [ ]


执行：

stack.push("{")


入栈后：

Stack: [ ( , [ , { ]
↑
栈顶

当前状态：

已经读取：([{
还未读取：}])

Stack: [ ( , [ , { ]

第 4 步：读取 }

当前字符是右大括号 }。

遇到右括号后，先看 Stack 是否为空。

Stack: [ ( , [ , { ]

Stack 不为空，可以继续比较。

右大括号 } 需要匹配：

{

当前 Stack 栈顶正好是 {。

当前右括号：}

需要的左括号：{

Stack 栈顶：{

比较结果：

{ ↔ }

匹配成功

因此将 { 出栈。

出栈前：

Stack: [ ( , [ , { ]
↑


执行：

stack.pop()


出栈后：

Stack: [ ( , [ ]
↑

当前状态：

已经读取：([{}
还未读取：])

Stack: [ ( , [ ]

第 5 步：读取 ]

当前字符是右方括号 ]。

它需要匹配左方括号 [。

当前栈顶正好是 [：

当前右括号：]

需要的左括号：[

Stack 栈顶：[

比较：

[ ↔ ]

匹配成功

执行出栈：

出栈前：

Stack: [ ( , [ ]
↑


执行：

stack.pop()


出栈后：

Stack: [ ( ]
↑

当前状态：

已经读取：([{}]
还未读取：)

Stack: [ ( ]

第 6 步：读取 )

当前字符是右圆括号 )。

它需要匹配左圆括号 (。

当前 Stack 栈顶正好是 (。

当前右括号：)

需要的左括号：(

Stack 栈顶：(

比较：

( ↔ )

匹配成功

执行出栈：

出栈前：

Stack: [ ( ]
↑


执行：

stack.pop()


出栈后：

Stack: [ ]

现在字符串已经扫描结束。

Stack 也为空。

所有左括号都找到了对应的右括号
所有括号的关闭顺序也正确

结果：true

七、完整过程汇总

最后 Stack 为空，因此返回：

true

八、失败示例一：(]

字符串：

( ]

第 1 步

读取 (，左括号入栈。

Stack: [ ( ]

第 2 步

读取 ]。

] 需要匹配的左括号是 [。

但是当前 Stack 栈顶是 (。

当前右括号：]

需要的左括号：[

实际栈顶：(

比较：

( ≠ [

括号类型不同，所以立即返回：

false

这里的问题不是括号数量，而是括号类型不匹配。

九、失败示例二：([)]

这个例子更容易让人困惑。

字符串中有：

一对圆括号
一对方括号

括号数量和类型看起来都没问题，但关闭顺序错了。

字符串：

( [ ) ]

先读取前两个左括号：

读取 (：

Stack: [ ( ]
读取 [：

Stack: [ ( , [ ]
↑
栈顶

接下来读取 )。

) 需要匹配 (。

但当前栈顶是最近进入的 [：

当前右括号：)

需要的左括号：(

实际栈顶：[

比较：

[ ≠ (

因此返回：

false

不能越过还没有关闭的 [，去寻找下面的 (。

错误结构：

( [ ) ]
↑ ↑

圆括号跨过了方括号

正确结构应该是：

( [ ] )
↑ ↑
↑ ↑

这也说明，括号匹配不能只看数量，还必须检查嵌套顺序。

十、失败示例三：第一个字符就是右括号

字符串：

")("

第一个字符是 )。

此时：

Stack: [ ]

Stack 为空，说明前面没有左圆括号可以和它配对。

流程如下：

读取右括号 )
│
▼
Stack 是否为空？
│
是
│
▼
返回 false

因此不需要继续扫描后面的字符。

十一、失败示例四：扫描结束后 Stack 不为空

看这个字符串：

"((("

三个字符都是左括号。

它们会依次入栈：

读取第一个 (：

Stack: [ ( ]
读取第二个 (：

Stack: [ ( , ( ]
读取第三个 (：

Stack: [ ( , ( , ( ]

字符串已经扫描完了，但 Stack 里还剩三个左括号。

这意味着它们没有对应的右括号。

所以最后不能直接返回 true，而是必须检查：

Stack 是否为空？

此时 Stack 不为空，所以结果是：

false

十二、JavaScript 解法

function isValid(s) {
// 有效括号一定成对出现。
// 如果字符串长度是奇数，可以直接返回 false。
if (s.length % 2 !== 0) {
return false;
}

const stack = [];

// 每种右括号对应的左括号
const pairs = {
")": "(",
"]": "[",
"}": "{"
};

for (const char of s) {
// 遇到左括号，直接入栈
if (char === "(" || char === "[" || char === "{") {
stack.push(char);
continue;
}

// 遇到右括号时，如果 Stack 为空，
// 说明没有左括号可以和它匹配
if (stack.length === 0) {
return false;
}

// 查看最近进入 Stack 的左括号
const top = stack.pop();

// 检查括号类型是否匹配
if (top !== pairs[char]) {
return false;
}
}

// Stack 为空，说明所有括号都完成了配对
return stack.length === 0;
}

十三、代码流程逐行解释

1. 创建 Stack

const stack = [];

JavaScript 中可以使用数组模拟 Stack。

主要使用两个方法：

stack.push()

负责入栈。

stack.pop()

负责出栈。

2. 建立括号对应关系

const pairs = {
")": "(",
"]": "[",
"}": "{"
};

这张表表示：

遇到 )，栈顶必须是 (
遇到 ]，栈顶必须是 [
遇到 }，栈顶必须是 {

例如当前字符是 ]：

pairs["]"]

得到：

[

因此代码可以检查：

top !== pairs[char]

也就是：

实际栈顶
是否等于
当前右括号需要的左括号

3. 遇到左括号就入栈

if (char === "(" || char === "[" || char === "{") {
stack.push(char);
continue;
}

例如当前 Stack 是：

[ ( , [ ]

当前字符是 {：

stack.push("{");

结果变成：

[ ( , [ , { ]

continue 表示当前字符处理完了，继续读取下一个字符。

4. 遇到右括号先检查空栈

if (stack.length === 0) {
return false;
}

例如：

输入："]"

此时没有任何左括号入栈。

Stack: [ ]

右括号没有可以匹配的对象，所以直接返回 false。

5. 取出栈顶左括号

const top = stack.pop();

例如：

出栈前：

Stack: [ ( , [ , { ]

执行：

const top = stack.pop();

top 得到：

{

Stack 变成：

Stack: [ ( , [ ]

6. 检查括号类型

if (top !== pairs[char]) {
return false;
}

假设当前字符是：

}

那么：

pairs["}"]

结果是：

{

如果刚刚出栈的 top 也是 {，说明匹配成功。

如果 top 是 [ 或 (，说明括号类型不匹配，直接返回 false。

7. 最后检查 Stack

return stack.length === 0;

扫描结束后有两种情况。

Stack 为空

Stack: [ ]

说明所有左括号都已经被正确关闭。

返回：

true

Stack 不为空

Stack: [ ( , [ ]

说明还有左括号没有找到对应的右括号。

返回：

false

十四、Python 解法

def isValid(s: str) -> bool:
if len(s) % 2 != 0:
return False

stack = []

pairs = {
")": "(",
"]": "[",
"}": "{"
}

for char in s:
if char in "([{":
stack.append(char)
continue

if not stack:
return False

top = stack.pop()

if top != pairs[char]:
return False

return len(stack) == 0

Python 中：

stack.append(char)

相当于入栈。

stack.pop()

相当于出栈。

整体思路与 JavaScript 完全相同。

十五、时间复杂度和空间复杂度

假设字符串长度为 n。

时间复杂度：O(n)

每个字符只需要从左到右读取一次。

每个左括号最多入栈一次，每个匹配成功的左括号最多出栈一次。

因此时间复杂度是：

O(n)

空间复杂度：O(n)

最坏情况下，字符串全部都是左括号：

(((([[{{

这些左括号都需要暂时保存在 Stack 中。

所以最坏情况下，Stack 的大小与字符串长度相同。

空间复杂度是：

O(n)

十六、常见错误

错误一：只统计括号数量

有人会分别统计：

( 和 ) 的数量
[ 和 ] 的数量
{ 和 } 的数量

但下面这个字符串中，各类括号数量完全相同：

([)]

结果仍然是无效的。

因为括号匹配不仅要看数量，还要看关闭顺序。

错误二：遇到右括号就直接出栈

错误写法：

const top = stack.pop();

在出栈前没有检查 Stack 是否为空。

例如输入：

")"

此时 Stack 中没有任何左括号。

正确做法是先检查：

if (stack.length === 0) {
return false;
}

错误三：只要是左括号就算匹配

下面的字符串中，确实有一个左括号和一个右括号：

(]

但它们类型不同。

必须严格检查：

( 只能匹配 )
[ 只能匹配 ]
{ 只能匹配 }

错误四：扫描结束后直接返回 true

例如：

"((("

扫描过程中没有出现错误的右括号，但左括号始终没有关闭。

因此扫描结束后必须判断：

stack.length === 0

十七、面试时怎么解释？

面试中可以这样回答：

这道题需要判断每个右括号，是否与最近一个尚未匹配的左括号配对。最近出现的左括号需要最先关闭，符合 Stack 后进先出的特点。

遍历字符串时，遇到左括号就入栈；遇到右括号时，先检查 Stack 是否为空，然后比较栈顶左括号是否与当前右括号匹配。匹配成功就出栈，不匹配就立即返回 false。

字符串遍历结束后，只有 Stack 为空，才说明所有括号都完成了正确配对。

时间复杂度是 O(n)，空间复杂度是 O(n)。

十八、最后总结

Valid Parentheses 最重要的一句话是：

当前右括号必须匹配最近出现、
并且尚未关闭的左括号。

“最近进入的左括号最先被关闭”，正好就是 Stack 的：

后进先出
Last In, First Out

完整流程可以记成四步：

1. 遇到左括号：入栈

2. 遇到右括号：
先检查 Stack 是否为空

3. 比较右括号和栈顶左括号：
匹配就出栈，不匹配就返回 false

4. 扫描结束：
Stack 为空返回 true
Stack 不为空返回 false

真正理解入栈、检查栈顶和出栈的顺序后，这道题就不需要死记代码了。