LeetCode 20. Valid Parentheses：一道栈题的完整剖析——从算法原理到十种语言实现

• 示例工程

本文基于 doocs/leetcode 仓库中 20. Valid Parentheses 题解文档（中文版）展开，完整讲解「有效括号」这道经典栈题的题目定义、算法推导思路与时间/空间复杂度。读完后，你不仅能掌握"哈希表 + 栈"一次扫描判定括号序列合法性的核心方法，还能拿到仓库中 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Ruby、PHP 十种语言的完整可运行实现，并理解每种语言在"栈"这一抽象上的落地差异。

题目描述与有效性规则

给定一个只包含'('、')'、'{'、'}'、'['、']'这六种字符的字符串s，判断该输入字符串是否有效。一个有效字符串必须同时满足以下三条规则：

1. 同类型闭合：左括号必须由相同类型的右括号闭合（(只能由)闭合）；
2. 顺序正确：左括号必须以正确的顺序闭合（不允许交错嵌套）；
3. 一一对应：每个右括号都有一个对应的、相同类型的左括号。

仓库文档中给出了 5 个标准示例，覆盖了"全部合法、全部不合法、交叉不合法"等关键情形：

约束条件：

• 1 <= s.length <= 10^4；
• s仅由括号'()[]{}'组成（无其他字符，无需处理非法字符）。

思路分析：为什么"反复删除相邻括号"不是最优解

在仓库题解的思考（Thinking）部分中，先给出了一个直观但低效的候选方案：把相邻的()、[]、{}从字符串中反复删除，直到不能再删为止，最终若字符串为空则有效。这个思路在结果上是正确的，但问题在于性能：

• 每一轮删除都要重新扫描整个字符串，当n <= 10^4且输入为深度嵌套（如"((((...))))）时，最坏情况会退化为O(n²)，容易超时。

真正的瓶颈在于：配对并不只取决于相邻的两个字符。后出现的左括号必须先被闭合，更早出现的左括号还要留在原处等待；一旦出现([)]这种交错结构，"删除相邻括号"这类局部操作就无法把字符串消成空串——它根本无法表达"谁必须等谁先闭合"这种全局约束。

正确的观察是：括号匹配是后进先出（LIFO）的——当前遇到的右括号，其唯一合法的配对对象就是最近一个尚未闭合的左括号。而"后进先出"正是栈的定义：

• 读到左括号时，把它对应的右括号压入栈顶——相当于把"下一步只允许出现哪个右括号"放在最上面；
• 读到右括号时，只与栈顶比较：不相等说明类型或顺序已经错了，可以直接返回false；
• 扫描结束后栈若仍非空，说明还有左括号从未被闭合，同样返回false。

解法：哈希表 + 栈，一次扫描 O(n)

具体算法（对应 Solution.py）：

1. 用哈希表d记录每种左括号对应的右括号：{ '(' : ')' , '[' : ']' , '{' : '}' }；
2. 用栈stk保存"尚未匹配的右括号"；
3. 从左到右扫描s：
   • 当前字符是左括号（c in d）：将d[c]（它要求的右括号）压入栈；
   • 当前字符是右括号：若栈为空，或弹出的栈顶与该字符不相等，立即返回false；
4. 扫描结束后，栈为空返回true，否则返回false。

下面按仓库源码逐一给出十种语言的完整实现（与 README_EN.md 中 Solution 1: Stack 章节一致），并在每段代码后说明实现细节。

Python3

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

对应 Solution.py 第 3~9 行。Python 列表list天然充当栈，append/pop即为入栈出栈。注意第 8 行elif not stk or stk.pop() != c利用了短路求值：栈为空时直接判负，不会触发pop的IndexError——这是处理"右括号无配对左括号"（如输入")("）的关键防御。

Java

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(); } }

对应 Solution.java。两个值得注意的细节：

• 栈选用ArrayDeque<Character>而非Stack类——Deque接口的push/pop是面向数组实现的，Stack继承自过时的Vector（每次操作都要同步加锁），用ArrayDeque作为栈是 Java 社区的标准做法；
• 哈希表初始容量显式指定为new HashMap<>(3)，恰好容纳 3 个键值对，避免扩容。

C++

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(); } };

对应 Solution.cpp 第 3~16 行。这里有一个很务实的取舍：直接用std::string当栈——push_back/back/pop_back恰好就是栈操作，而且连续char存储比std::stack<char>少一层封装、缓存友好。另外d.contains(c)是 C++20 的写法（等价于d.find(c) != d.end()），编译时需保证语言标准不低于 C++20。

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 }

对应 Solution.go。Go 没有内置栈类型，这里用[]byte切片实现：append入栈，出栈则是stk = stk[:len(stk)-1]这种重新切片的技巧——因为括号都是 ASCII 单字节字符，用byte而不是rune切片更省内存、查表更快。

TypeScript

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。for...of按码元遍历字符串，d.get(c)!中的非空断言!是因为 TS 类型系统中Map.get返回T | undefined，而此处已由d.has(c)保证键存在。注意此版本省略了stk空判断——stk为空时stk.pop()返回undefined，undefined !== c恒为真，自然返回false，语义上是安全的，但也因此少了一次"栈空即判负"的显式语义。

Rust

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() } }

对应 Solution.rs。Rust 用Vec<char>作栈，其惯用法体现在两处：Vec::pop返回Option<char>，所以与Some(c)比较即可同时覆盖"栈空"和"不匹配"两种失败；if let Some(&v) = d.get(&c)是查表并解引用的标准模式，避免对char做无谓拷贝。

JavaScript

/** * @param {string} s * @return {boolean} */ var isValid = function (s) { const d = new Map([ ['(', ')'], ['[', ']'], ['{', '}'], ]); const stk = []; 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.js。使用Map而非普通对象作映射，因为键是括号符号，Map对任意键类型都保持 O(1) 且不会与对象原型键冲突。

C#

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; } }

对应 Solution.cs。这是十种实现中少数显式使用语言自带栈容器（Stack<char>）的版本，foreach (char c in s)直接对字符串做字符枚举。

Ruby

# @param {String} s # @return {Boolean} 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

对应 Solution.rb。Ruby 中用Hash+Array组合，方法名统一为蛇形is_valid（LeetCode Ruby 判题签名风格）。

PHP

class Solution { /** * @param String $s * @return Boolean */ 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); } }

对应 Solution.php。PHP 惯用数组 +array_pop模拟栈，比较时使用严格全等!==，避免类型强制转换带来的误判。

复杂度分析

对所有实现，时间复杂度均为O(n)：每个字符只做常数次的哈希查找与栈操作，单次线性扫描。空间复杂度为O(n)：最坏情况下（如全部为左括号）栈中会保存 n/2 个元素；哈希表大小恒为常数 3。

运行示例：逐步跟踪 "([)]" 为什么失败

以示例 5 的s = "([)]"为例，按栈算法逐步跟踪（这正是文档思考部分强调"局部删除无法消空"的交叉情形）：

栈顶保存的是"下一次允许出现的右括号"，第 3 步栈顶是]（因为[是最近未闭合的左括号），而实际到来的是)——类型或顺序错误，算法在 O(n) 内提前终止。反之，合法嵌套"([])"的跟踪为：(压)→[压]→ 弹]匹配 → 弹)匹配 → 结束时空栈，返回true。而输入")("这类"右括号无左括号"的边界情形，会在第 1 步触发"栈为空"分支返回false，不会发生空栈弹出异常。

小结

这道 LeetCode 20 题的价值在于用最少的代码量展示了栈的核心抽象——用 LIFO 结构维护"未完成的事务"：

• 关键设计是"左括号入栈时存入其对应的右括号"，使后续匹配退化为一次栈顶比较，哈希表 + 栈各自只做一件事；
• 三类失败模式各有归口：类型错误（栈顶不等）、顺序错误（交叉嵌套时栈顶不等）、无配对右括号（空栈弹出）与未闭合左括号（结束时栈非空）；
• 仓库中十种语言的实现 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs、Solution.rb、Solution.php 算法骨架完全一致，差异仅在各语言对"栈"这一抽象的落地方式（列表/ArrayDeque/std::string/[]byte切片/Vec等），适合作为跨语言对照学习的范本。

• 示例工程