LeetCode 20 有效的括号：基于栈的括号序列校验算法与十语言实现解析-平芜编程栈

示例工程

【免费下载链接】leetcode

🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

本篇技术指南以 LeetCode 20 有效的括号题解为主体，完整讲解“有效括号序列”的判定规则、从 O(n²) 反复删除法退化到栈扫描法 O(n) 的思路推导，以及该仓库中 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Ruby、PHP 十种语言的参考实现。读完后可掌握栈在“后进先出配对”场景中的标准用法，并能对照各语言实现理解栈结构细节与边界条件的处理方式。

题目描述

给定一个只包括'('、')'、'{'、'}'、'['、']'的字符串s，判断字符串是否有效。有效字符串需满足三条规则：

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

题目给出的 5 个示例覆盖了“简单配对、多类嵌套、类型错配、合法嵌套、交错嵌套”五种典型形态：

输入	输出	说明
`s = "()"`	`true`	单对括号直接闭合
`s = "()[]{}"`	`true`	多类括号依次独立闭合
`s = "(]"`	`false`	右括号类型与左括号不匹配
`s = "([])"`	`true`	括号层层嵌套，内层先闭合
`s = "([)]"`	`false`	交错嵌套，内层未闭合时外层先闭合

约束条件：1 <= s.length <= 10^4，且s仅由括号'()[]{}'组成。约束保证了单次线性扫描在任意语言下都绰绰有余，算法设计的关键在于“用什么结构记录尚未闭合的左括号”。

解法思路：从 O(n²) 反复删除到栈扫描

原题解在 README.md 的“思考”一节中给出了完整的思路演进过程，值得逐段理解：

直觉方案及其缺陷：最朴素的思路是把已经相邻的()、[]、{}反复从字符串中删去，直到不能再删，若字符串为空则合法。这一方案的正确性没有问题，但每一轮删除都要重新扫描整个字符串，当n <= 10^4时最坏会退化成O(n²)；对于(开头大量嵌套的输入，层层剥除极易超时。

瓶颈定位：配对并不只看相邻的两个字符。后出现的左括号必须先被闭合，更早压下的左括号还要留在原处等待；像([)]这种交错结构，任何“局部相邻删除”都无法把字符串消成空串。

关键洞察——后进先出：当前右括号唯一合法的对象，是最近一个尚未闭合的左括号。这正是栈（LIFO）的语义：

读到左括号时，把与之对应的右括号压入栈顶——相当于把“下一次允许出现的右括号”放在最上面；
读到右括号时，只与栈顶比较：栈为空（没有可配对的左括号）或弹出的字符与当前右括号不相等（类型或顺序已错），立即返回false；
扫描结束后，若栈中仍有元素，说明存在没有闭合的左括号，返回false；栈为空则返回true。

把“左括号 → 对应右括号”的映射存入哈希表d，则左括号入栈、右括号比对两个分支可以统一由c in d这一条件驱动，这是十种语言实现共同遵循的骨架。

方法一：栈（核心算法）

算法的完整步骤如下：

初始化哈希表d = { '(' : ')' , '[' : ']' , '{' : '}' }和空栈stk；
从左到右扫描s中的每个字符c：
- 若c是左括号（c in d）：将d[c]压入stk；
- 否则（c是右括号）：若stk为空，或stk.pop()的结果与c不相等，返回false；
扫描结束后，stk为空则返回true，否则返回false。

时间复杂度：$O(n)$，其中 $n$ 为字符串s的长度。每个字符只做一次哈希查找与最多一次出栈操作，均为 $O(1)$。空间复杂度：$O(n)$，最坏情况下（如((((...全是左括号）栈深达到 $n$。

Python3 参考实现

仓库中的 Solution.py 是最贴近算法描述的版本：

class Solution: def isValid(self, s: str) -> bool: stk = [] d = {'(': ')', '[': ']', '{': '}'} for c in s: if c in d: stk.append(d[c]) elif not stk or stk.pop() != c: return False return not stk

几个值得注意的细节：

用列表stk充当栈，append是入栈、pop()是出栈，均为均摊 $O(1)$；
Solution.py 的elif not stk or stk.pop() != c一行同时处理了栈空越界（遇到形如")("的输入时直接返回false）和类型不匹配两种失败情形，短路求值保证空栈时不会调用pop()；
末尾return not stk利用列表的真值性判断“是否所有左括号都已闭合”。

Java 参考实现

Solution.java 使用ArrayDeque作为栈、HashMap存映射：

class Solution { public boolean isValid(String s) { Deque<Character> stk = new ArrayDeque<>(); Map<Character, Character> d = new HashMap<>(3); d.put('(', ')'); d.put('[', ']'); d.put('{', '}'); for (char c : s.toCharArray()) { if (d.containsKey(c)) { stk.push(d.get(c)); } else if (stk.isEmpty() || stk.pop() != c) { return false; } } return stk.isEmpty(); } }

这里刻意选用ArrayDeque而非Stack（后者继承自Vector，方法同步且性能差）；push/pop分别对应入栈与出栈；
映射键只有 3 个，new HashMap<>(3)指定初始容量可以避免不必要的扩容；
与 Python 版一致，stk.isEmpty() || stk.pop() != c依赖短路求值防止空栈弹出。

C++ 参考实现

Solution.cpp 直接用一个string充当栈体，省去了引入<stack>的开销：

class Solution { public: bool isValid(string s) { string stk; unordered_map<char, char> d{{'(', ')'}, {'[', ']'}, {'{', '}'}}; for (char c : s) { if (d.contains(c)) { stk.push_back(d[c]); } else if (stk.empty() || stk.back() != c) { return false; } else { stk.pop_back(); } } return stk.empty(); } };

以string的尾部模拟栈：push_back入栈、back()取栈顶、pop_back()出栈，字符按字节连续存储，缓存友好；
与栈类容器不同，string版把“取栈顶”和“弹出”拆成了两步（Solution.cpp），先用stk.back() != c比较，匹配成功后再pop_back()，逻辑上等价于其他语言的“弹出后比较”；
d.contains(c)依赖 C++20 的unordered_map::contains接口。

Go 参考实现

Solution.go 用字节切片模拟栈：

func isValid(s string) bool { stk := []byte{} d := map[byte]byte{'(': ')', '[': ']', '{': '}'} for i := 0; i < len(s); i++ { c := s[i] if v, ok := d[c]; ok { stk = append(stk, v) } else if len(stk) == 0 || stk[len(stk)-1] != c { return false } else { stk = stk[:len(stk)-1] } } return len(stk) == 0 }

由于输入只含 6 种 ASCII 括号，[]byte（等价于[]rune的单字节场景）足够承载栈元素，append与切片截断均为均摊 $O(1)$；
Solution.go 通过stk = stk[:len(stk)-1]重设切片长度来“弹出”栈顶，复用了已分配的底层数组，无需额外内存操作。

TypeScript 参考实现

Solution.ts 用Map存映射、数组模拟栈：

function isValid(s: string): boolean { const d = new Map<string, string>([ ['(', ')'], ['[', ']'], ['{', '}'], ]); const stk: string[] = []; for (const c of s) { if (d.has(c)) { stk.push(d.get(c)!); } else if (stk.pop() !== c) { return false; } } return stk.length === 0; }

注意 Solution.ts 与 Solution.js（JavaScript 版实现相同）这里没有显式判空：JS 数组对空栈调用pop()会返回undefined，而undefined !== c必然成立，因此“栈为空”和“类型不匹配”两种失败情形被同一行代码自然覆盖，写法比强类型语言更简洁。

Rust 参考实现

Solution.rs 用Vec<char>模拟栈、HashMap存映射：

use std::collections::HashMap; impl Solution { pub fn is_valid(s: String) -> bool { let d: HashMap<char, char> = [('(', ')'), ('[', ']'), ('{', '}' )] .iter() .copied() .collect(); let mut stk = Vec::new(); for c in s.chars() { if let Some(&v) = d.get(&c) { stk.push(v); } else if stk.pop() != Some(c) { return false; } } stk.is_empty() } }

仓库实现将映射字面量写成[('(', ')'), ('[', ']'), ('{', '}')]后经iter().copied().collect()收集为HashMap<char, char>；
Solution.rs 的stk.pop() != Some(c)同样利用了类型系统：空栈弹出返回None，None != Some(c)恒真，从而与 JS 版一样免去了显式判空分支；
末尾stk.is_empty()作为尾表达式隐式返回bool。

C# 参考实现

Solution.cs 直接使用标准库的Stack<char>与Dictionary<char, char>：

public class Solution { public bool IsValid(string s) { Stack<char> stk = new Stack<char>(); Dictionary<char, char> d = new Dictionary<char, char>(); d.Add('(', ')'); d.Add('[', ']'); d.Add('{', '}'); foreach (char c in s) { if (d.ContainsKey(c)) { stk.Push(d[c]); } else if (stk.Count == 0 || stk.Pop() != c) { return false; } } return stk.Count == 0; } }

Stack<T>的Push/Pop是 $O(1)$ 操作；空栈判断通过stk.Count == 0完成，其余控制流与其他强类型语言完全同构。

Ruby 参考实现

Solution.rb 用数组模拟栈：

def is_valid(s) stk = [] d = { '(' => ')', '[' => ']', '{' => '}' } s.each_char do |c| if d.key?(c) stk.push(d[c]) elsif stk.empty? || stk.pop != c return false end end stk.empty? end

PHP 参考实现

Solution.php 用原生数组与array_pop模拟栈：

class Solution { function isValid($s) { $stk = []; $d = [ '(' => ')', '[' => ']', '{' => '}', ]; $n = strlen($s); for ($i = 0; $i < $n; $i++) { $c = $s[$i]; if (isset($d[$c])) { $stk[] = $d[$c]; } elseif (empty($stk) || array_pop($stk) !== $c) { return false; } } return empty($stk); } }

其中isset($d[$c])兼作“是否为左括号”的判断与取值依据，array_pop返回被弹出的栈顶并同步缩减数组，配合empty($stk)的宽松判空完成收尾检查。

用示例手工推演：栈状态如何随扫描变化

以 5 个示例逐字符跟踪栈内容，可以验证算法每一步的正确性（→表示该字符处理后栈的状态，#表示立即返回false）：

字符	动作	栈状态
`s = "()"`	`(`压入`)`；`)`弹出`)`相等	`[]`→ 返回`true`
`s = "()[]{}"`	每对括号压入后立即弹出	始终`[]`→ 返回`true`
`s = "(]"`	`(`压入`)`；`]`弹出`)`不相等	立即`false`
`s = "([])"`	`(`压`)`、`[`压`]`、`[`前字符弹出`]`相等、`)`弹出`)`相等	`[]`→ 返回`true`
`s = "([)]"`	`(`压`)`、`[`压`]`；遇`)`弹出`]`不相等	立即`false`

两个额外的边界形态同样能正确覆盖：

s = ")("：第一个字符是右括号而栈为空，stk.empty() || ...（或 JS/Rust 中pop()返回空值）直接返回false；
s = "((("：扫描结束栈中残留 3 个)，stk.empty()为假，返回false。

这与题目“左括号必须有对应右括号、右括号不能凭空出现”的规则一一对应：栈空时遇到右括号对应右括号无主，扫描后栈非空对应左括号未闭合，栈顶不匹配对应类型或顺序错误——三条失败路径恰好覆盖三类非法形态。

跨语言实现的细节差异

对照 solution/0000-0099/0020.Valid Parentheses/ 目录下的全部源码文件，十种实现共享同一套算法骨架，差异集中在栈载体与判空方式上：

语言	栈载体	映射结构	判空方式
Python3	`list`（`append`/`pop`）	`dict`	`not stk`
Java	`ArrayDeque`（`push`/`pop`）	`HashMap`	`stk.isEmpty()`显式判空
C++	`string`（`push_back`/`pop_back`）	`unordered_map`	`stk.empty()`显式判空
Go	`[]byte`（`append`/切片截断）	`map[byte]byte`	`len(stk) == 0`显式判空
TypeScript	数组（`push`/`pop`）	`Map`	空栈`pop()`返回`undefined`，免判空
JavaScript	数组（`push`/`pop`）	`Map`	同 TypeScript
Rust	`Vec<char>`（`push`/`pop`）	`HashMap`	空栈`pop()`返回`None`，免判空
C#	`Stack<char>`	`Dictionary`	`stk.Count == 0`显式判空
Ruby	数组（`push`/`pop`）	字面量 Hash	`stk.empty?`显式判空
PHP	数组（`array_pop`）	数组	`empty($stk)`显式判空

从源码结构看，差异背后有两条一致的设计取舍：

映射方向统一为“左括号 → 右括号”：入栈时压入的是期望闭合它的右括号，而不是左括号本身。这样比较逻辑恒为“弹出的期望值 === 当前实际值”，避免了维护双向映射；
动态语言借语言特性简化分支：JavaScript / TypeScript 中空数组pop()返回undefined、Rust 中Vec::pop()返回None，两者与真实右括号字符永不相等，因此可以把“栈空”和“不匹配”合并成单行判断；而 Java、C++、Go、C#、Ruby、PHP 等则需要先显式判空再弹出，避免空栈异常（如 C#Stack.Pop()对空栈会抛出InvalidOperationException）。

这一细节也提示：在强类型语言移植此类栈式校验时，判空分支不是防御性冗余，而是正确性的一部分。

仓库中的相关文件

文件	说明
README.md	中文题解（题目描述、思考过程与全部代码）
README_EN.md	英文题解
Solution.py	Python3 实现
Solution.java	Java 实现
Solution.cpp	C++ 实现
Solution.go	Go 实现
Solution.ts	TypeScript 实现
Solution.rs	Rust 实现
Solution.js	JavaScript 实现
Solution.cs	C# 实现
Solution.php	PHP 实现
Solution.rb	Ruby 实现

小结

LeetCode 20 是“栈解决配对问题”的入门范例，其要点可以浓缩为三句话：

匹配是 LIFO 的：右括号唯一合法的配对对象是最近未闭合的左括号，因此用栈记录“尚待闭合”的期望右括号；
一次线性扫描即可判定：哈希表 $O(1)$ 查映射 + 栈 $O(1)$ 入出栈，整体时间复杂度 $O(n)$、空间复杂度 $O(n)$，彻底避免了反复删除相邻对的 $O(n²)$ 退化；
三条失败路径对应三类非法形态：栈空遇右括号（右括号无主）、栈顶不匹配（类型或顺序错误）、扫完栈非空（左括号未闭合），理解这三点即可正确推导并审查任意语言的实现。