算法刷题第18天｜LeetCode 20. 有效的括号——栈的经典入门应用

算法刷题第18天｜LeetCode 20. 有效的括号——栈的经典入门应用

今天是算法刷题的第18天，刷到了栈最经典的入门题：有效的括号。这道题看似简单，却完美体现了栈“先进后出”的核心思想，非常适合用来巩固栈的基础用法。

一、题目回顾

题目链接：https://leetcode.cn/problems/valid-parentheses/
视频讲解：https://www.bilibili.com/video/BV1AF411w78g

给定一个只包含 ()[]{} 的字符串，判断是否有效：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确顺序闭合
3. 每个右括号都有对应的左括号

示例：

- () → true
- ()[]{} → true
- (] → false
- ([)] → false
- ([]) → true

二、为什么用栈？

括号匹配的本质是：
后出现的左括号，要最先被闭合
→ 完全符合栈 后进先出（LIFO） 的特性。

生活里也很像：
先穿内衣→毛衣→外套，脱的时候必须先脱外套，再脱毛衣，最后脱内衣。
括号嵌套也是一样，最内层先闭合。

三、解题思路（标准栈解法）

1. 先做剪枝：字符串长度为奇数，直接返回 false （不可能成对）
2. 建一个栈，存未匹配的左括号
3. 遍历每个字符：
- 遇到左括号 ( [[__LINK_ICON]](https://leetcode.cn/problems/valid-parentheses/solutions/3958485/zhan-mo-ni-zhan-pi-pei-fa-by-an-cang-xua-zgok/?f_link_type=f_linkinlinenote&flow_extra=eyJpbmxpbmVfZGlzcGxheV9wb3NpdGlvbiI6MCwiZG9jX3Bvc2l0aW9uIjowLCJkb2NfaWQiOiJmOGNhNjcxZmFhYTMxN2ZiLTAxN2U3ZjgxZjViOTQ1N2EifQ%3D%3D&inline_doc_id=f8ca671faaa317fb-017e7f81f5b9457a)[ { → 入栈
- 遇到右括号：
- 栈空 → 无匹配左括号 → false
- 栈顶不匹配 → false
- 匹配 → 出栈
4. 遍历结束，栈必须为空才算全部匹配成功

四、代码实现（Python）

python
def isValid(s: str) -> bool:
# 奇数长度直接返回
if len(s) % 2 != 0:
return False

stack = []
# 右括号 → 对应左括号 的映射
mapping = {')': '(', ']': '[', '}': '{'}

for c in s:
# 右括号
if c in mapping:
# 栈空 或 不匹配
if not stack or stack[-1] != mapping[c]:
return False
stack.pop()
# 左括号
else:
stack.append(c)

# 最终栈必须为空
return len(stack) == 0


五、复杂度分析

- 时间复杂度：O(n)
每个字符只遍历一次，入栈出栈都是 O(1)
- 空间复杂度：O(n)
最坏情况全是左括号，栈存全部字符