当前位置：首页 > news >正文

栈题解——有效的括号【LeetCode】两种方法

news 2025/7/19 22:21:38

20. 有效的括号

方法一：保存括号

一、算法逻辑（逐步通顺讲解每一步思路）

这道题目要求我们判断一个仅包含 '(', ')', '{', '}', '[', ']' 的字符串 s 是否是合法的括号表达式。合法规则包括：

左右括号必须匹配；
括号必须以正确的顺序闭合（后开的先闭）。

这段代码使用了 栈（stack）结构 来模拟括号匹配的过程。

✅ 1️⃣ 特判：奇数长度必不合法

if len(s) % 2:return False

因为任何合法的括号组合，一定是成对出现，所以长度必须为偶数。

✅ 2️⃣ 准备映射表 `mp`

mp = {')': '(', ']': '[', '}': '{'}

该映射表用于在遇到右括号时，快速找出它对应的左括号。

✅ 3️⃣ 遍历字符串字符

初始化空栈 st = []，逐个扫描字符串中的每一个字符：

若为左括号：直接入栈；
若为右括号：
- 如果栈为空，说明没有配对的左括号 → 不合法；
- 否则弹出栈顶元素，判断是否是该右括号对应的左括号（即 st.pop() == mp[c]），不匹配即不合法。

✅ 4️⃣ 结束后检查栈是否清空

遍历结束后，所有左括号应该都被配对弹出，栈应为空：

return not st

若栈非空，说明存在多余未匹配的左括号。

二、核心点总结

✅ 采用 栈结构 LIFO（后进先出） 特性，完美解决成对闭合问题；
✅ 使用哈希表映射右括号对应的左括号，提升匹配判断效率；
✅ 入栈仅限左括号，出栈检查匹配右括号，逻辑清晰；
✅ len(s) % 2 的早期剪枝是一个实用的优化技巧。

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2:  # s 长度必须是偶数return Falsemp = {')': '(', ']': '[', '}': '{'}st = []for c in s:if c not in mp:  # c 是左括号st.append(c)  # 入栈elif not st or st.pop() != mp[c]:  # c 是右括号return False  # 没有左括号，或者左括号类型不对return not st  # 所有左括号必须匹配完毕

🔑 Python 中的字典 in 判断：

if c in mp: 或 if c not in mp:
👉 只检查 c 是否是 mp 的「键（key）」，不会检查值（value）。

三、时间复杂度分析

遍历字符串一次，每个字符最多入栈出栈一次；
所以总时间为 O(n)，其中 n = len(s)。

✅ 时间复杂度：O(n)

四、空间复杂度分析

栈最多存储 n 个字符（最坏情况为全是左括号）；
额外的映射表 mp 空间是常数级。

✅ 空间复杂度：O(n)

✅ 总结一句话

本算法用「栈」精准处理括号匹配问题，利用哈希映射和简洁判断逻辑，在 O(n) 时间 + O(n) 空间下完成合法性判断，是栈结构在语法解析中应用的经典模板。

方法二：if - else

一、算法逻辑（逐步通顺讲解每一步思路）

本解法仍然使用 栈（stack）结构，但其与标准写法最大的区别是：

✅ 将“期望的右括号”直接入栈，而不是左括号。

这样，当我们遇到一个右括号时，可以直接检查它是否等于栈顶元素，省去了映射匹配的过程，使逻辑更清晰直接。

✅ 1️⃣ 长度奇数必定非法

if len(s) % 2:return False

合法的括号必须成对存在，奇数长度直接排除。

✅ 2️⃣ 遍历每个字符，维护栈结构

初始化空栈 st = []。

如果当前字符 c 是左括号（(、[、{），则将它对应的右括号压入栈中；
```
if c == '(':st.append(')')
elif c == '[':st.append(']')
elif c == '{':st.append('}')
```
此时，栈内保存的是“我希望未来匹配的右括号”。
否则 c 是右括号，需要进行匹配：
```
elif not st or st.pop() != c:return False
```
若栈为空或弹出的不是当前括号 c，说明匹配失败。

✅ 3️⃣ 检查栈是否清空

所有字符扫描完后，栈应为空（表示所有匹配成功）：

return not st

二、核心点总结

✅ 本解法的亮点在于 直接将期望的右括号入栈，让后续匹配变得更简单：只需判断当前字符是否等于栈顶元素。
✅ 避免了显式使用映射表 {')': '(', ...}，逻辑更直观、写法更紧凑。
✅ 属于「期望匹配法」，是对传统「栈结构 + 哈希映射」解法的优化与改写，结构更清晰。

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2:  # s 长度必须是偶数return Falsest = []for c in s:if c == '(':st.append(')')  # 入栈对应的右括号elif c == '[':st.append(']')elif c == '{':st.append('}')elif not st or st.pop() != c:  # c 是右括号return False  # 没有左括号，或者左括号类型不对return not st  # 所有左括号必须匹配完毕