示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 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) { DequeCharacter stk new ArrayDeque(); MapCharacter, 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_mapchar, 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)依赖 C20 的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 Mapstring, 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.jsJavaScript 版实现相同这里没有显式判空JS 数组对空栈调用pop()会返回undefined而undefined ! c必然成立因此“栈为空”和“类型不匹配”两种失败情形被同一行代码自然覆盖写法比强类型语言更简洁。Rust 参考实现Solution.rs 用Vecchar模拟栈、HashMap存映射use std::collections::HashMap; impl Solution { pub fn is_valid(s: String) - bool { let d: HashMapchar, 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()收集为HashMapchar, charSolution.rs 的stk.pop() ! Some(c)同样利用了类型系统空栈弹出返回NoneNone ! Some(c)恒真从而与 JS 版一样免去了显式判空分支末尾stk.is_empty()作为尾表达式隐式返回bool。C# 参考实现Solution.cs 直接使用标准库的Stackchar与Dictionarychar, charpublic class Solution { public bool IsValid(string s) { Stackchar stk new Stackchar(); Dictionarychar, char d new Dictionarychar, 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; } }StackT的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? endPHP 参考实现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 ()(压入))弹出)相等[]→ 返回trues ()[]{}每对括号压入后立即弹出始终[]→ 返回trues (](压入)]弹出)不相等立即falses ([])(压)、[压]、[前字符弹出]相等、)弹出)相等[]→ 返回trues ([)](压)、[压]遇)弹出]不相等立即false两个额外的边界形态同样能正确覆盖s )(第一个字符是右括号而栈为空stk.empty() || ...或 JS/Rust 中pop()返回空值直接返回falses (((扫描结束栈中残留 3 个)stk.empty()为假返回false。这与题目“左括号必须有对应右括号、右括号不能凭空出现”的规则一一对应栈空时遇到右括号对应右括号无主扫描后栈非空对应左括号未闭合栈顶不匹配对应类型或顺序错误——三条失败路径恰好覆盖三类非法形态。跨语言实现的细节差异对照 solution/0000-0099/0020.Valid Parentheses/ 目录下的全部源码文件十种实现共享同一套算法骨架差异集中在栈载体与判空方式上语言栈载体映射结构判空方式Python3listappend/popdictnot stkJavaArrayDequepush/popHashMapstk.isEmpty()显式判空Cstringpush_back/pop_backunordered_mapstk.empty()显式判空Go[]byteappend/切片截断map[byte]bytelen(stk) 0显式判空TypeScript数组push/popMap空栈pop()返回undefined免判空JavaScript数组push/popMap同 TypeScriptRustVeccharpush/popHashMap空栈pop()返回None免判空C#StackcharDictionarystk.Count 0显式判空Ruby数组push/pop字面量 Hashstk.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.pyPython3 实现Solution.javaJava 实现Solution.cppC 实现Solution.goGo 实现Solution.tsTypeScript 实现Solution.rsRust 实现Solution.jsJavaScript 实现Solution.csC# 实现Solution.phpPHP 实现Solution.rbRuby 实现小结LeetCode 20 是“栈解决配对问题”的入门范例其要点可以浓缩为三句话匹配是 LIFO 的右括号唯一合法的配对对象是最近未闭合的左括号因此用栈记录“尚待闭合”的期望右括号一次线性扫描即可判定哈希表 $O(1)$ 查映射 栈 $O(1)$ 入出栈整体时间复杂度 $O(n)$、空间复杂度 $O(n)$彻底避免了反复删除相邻对的 $O(n²)$ 退化三条失败路径对应三类非法形态栈空遇右括号右括号无主、栈顶不匹配类型或顺序错误、扫完栈非空左括号未闭合理解这三点即可正确推导并审查任意语言的实现。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐刷穿 LeetCode 20有效的括号——栈 哈希表与栈 ASCII 差值的双解法全解析刷穿 LeetCode 20有效的括号——栈 哈希表与栈 ASCII 差值的双解法全解析 本文是「宫水三叶的刷题日记」系列LogicStack Le教程文档LeetCode 1190 反转每对括号间的子串基于双端队列与栈的逐层括号反转全解LeetCode 1190 反转每对括号间的子串基于双端队列与栈的逐层括号反转全解 导读 本文围绕 LeetCode 中等题 1190. 反转每对括号间的子串教程文档带通配符的括号校验LeetCode 678「有效的括号字符串」双解法精讲动态规划 双端模拟带通配符的括号校验LeetCode 678「有效的括号字符串」双解法精讲动态规划 双端模拟 本篇技术指南以 LogicStack LeetCode 仓教程文档上一篇UAssetGUI零引擎依赖的虚幻引擎资产深度编辑独立工具终极指南下一篇光学衍射神经网络5步搭建下一代全光计算系统创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考