示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文基于 doocs/leetcode 仓库中 20. Valid Parentheses 题解文档中文版展开完整讲解「有效括号」这道经典栈题的题目定义、算法推导思路与时间/空间复杂度。读完后你不仅能掌握哈希表 栈一次扫描判定括号序列合法性的核心方法还能拿到仓库中 Python3、Java、C、Go、TypeScript、Rust、JavaScript、C#、Ruby、PHP 十种语言的完整可运行实现并理解每种语言在栈这一抽象上的落地差异。题目描述与有效性规则给定一个只包含(、)、{、}、[、]这六种字符的字符串s判断该输入字符串是否有效。一个有效字符串必须同时满足以下三条规则同类型闭合左括号必须由相同类型的右括号闭合(只能由)闭合顺序正确左括号必须以正确的顺序闭合不允许交错嵌套一一对应每个右括号都有一个对应的、相同类型的左括号。仓库文档中给出了 5 个标准示例覆盖了全部合法、全部不合法、交叉不合法等关键情形示例输入s输出说明1()true最简单的成对匹配2()[]{}true多组括号顺序相邻3(]false类型不匹配4([])true合法嵌套5([)]false典型交叉嵌套局部看似乎都有对应字符但顺序非法约束条件1 s.length 10^4s仅由括号()[]{}组成无其他字符无需处理非法字符。思路分析为什么反复删除相邻括号不是最优解在仓库题解的思考Thinking部分中先给出了一个直观但低效的候选方案把相邻的()、[]、{}从字符串中反复删除直到不能再删为止最终若字符串为空则有效。这个思路在结果上是正确的但问题在于性能每一轮删除都要重新扫描整个字符串当n 10^4且输入为深度嵌套如((((...))))时最坏情况会退化为O(n²)容易超时。真正的瓶颈在于配对并不只取决于相邻的两个字符。后出现的左括号必须先被闭合更早出现的左括号还要留在原处等待一旦出现([)]这种交错结构删除相邻括号这类局部操作就无法把字符串消成空串——它根本无法表达谁必须等谁先闭合这种全局约束。正确的观察是括号匹配是后进先出LIFO的——当前遇到的右括号其唯一合法的配对对象就是最近一个尚未闭合的左括号。而后进先出正是栈的定义读到左括号时把它对应的右括号压入栈顶——相当于把下一步只允许出现哪个右括号放在最上面读到右括号时只与栈顶比较不相等说明类型或顺序已经错了可以直接返回false扫描结束后栈若仍非空说明还有左括号从未被闭合同样返回false。解法哈希表 栈一次扫描 O(n)具体算法对应 Solution.py用哈希表d记录每种左括号对应的右括号{ ( : ) , [ : ] , { : } }用栈stk保存尚未匹配的右括号从左到右扫描s当前字符是左括号c in d将d[c]它要求的右括号压入栈当前字符是右括号若栈为空或弹出的栈顶与该字符不相等立即返回false扫描结束后栈为空返回true否则返回false。下面按仓库源码逐一给出十种语言的完整实现与 README_EN.md 中 Solution 1: Stack 章节一致并在每段代码后说明实现细节。Python3class 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——这是处理右括号无配对左括号如输入)(的关键防御。Javaclass 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(); } }对应 Solution.java。两个值得注意的细节栈选用ArrayDequeCharacter而非Stack类——Deque接口的push/pop是面向数组实现的Stack继承自过时的Vector每次操作都要同步加锁用ArrayDeque作为栈是 Java 社区的标准做法哈希表初始容量显式指定为new HashMap(3)恰好容纳 3 个键值对避免扩容。Cclass 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(); } };对应 Solution.cpp 第 3~16 行。这里有一个很务实的取舍直接用std::string当栈——push_back/back/pop_back恰好就是栈操作而且连续char存储比std::stackchar少一层封装、缓存友好。另外d.contains(c)是 C20 的写法等价于d.find(c) ! d.end()编译时需保证语言标准不低于 C20。Gofunc 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切片更省内存、查表更快。TypeScriptfunction 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。for...of按码元遍历字符串d.get(c)!中的非空断言!是因为 TS 类型系统中Map.get返回T | undefined而此处已由d.has(c)保证键存在。注意此版本省略了stk空判断——stk为空时stk.pop()返回undefinedundefined ! c恒为真自然返回false语义上是安全的但也因此少了一次栈空即判负的显式语义。Rustuse 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() } }对应 Solution.rs。Rust 用Vecchar作栈其惯用法体现在两处Vec::pop返回Optionchar所以与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) { 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; } }对应 Solution.cs。这是十种实现中少数显式使用语言自带栈容器Stackchar的版本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 中用HashArray组合方法名统一为蛇形is_validLeetCode Ruby 判题签名风格。PHPclass 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 ([)]为例按栈算法逐步跟踪这正是文档思考部分强调局部删除无法消空的交叉情形步字符c动作栈stk状态结果1(d命中压入)[)]继续2[d命中压入][), ]]继续3)弹出栈顶]]≠)—立即返回false栈顶保存的是下一次允许出现的右括号第 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等适合作为跨语言对照学习的范本。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 232 用栈实现队列双栈倒序法的原理剖析与三语言实现LeetCode 232 用栈实现队列双栈倒序法的原理剖析与三语言实现 导读 《用栈实现队列》是 LeetCode 高频笔试题也是理解用受限数据结构模拟另示例工程教程教育LeetCode 20 有效的括号基于栈的括号序列校验算法与十语言实现解析LeetCode 20 有效的括号基于栈的括号序列校验算法与十语言实现解析 本篇技术指南以 LeetCode 20 有效的括号题解 https://link.示例工程用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题 本文围绕 LeetCode 225「用队列实现栈」展开系统讲解双队列、单队列、队列示例工程上一篇WinPmem 开源项目教程下一篇MathJax 文档项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考