算法刷题第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_typef_linkinlinenoteflow_extraeyJpbmxpbmVfZGlzcGxheV9wb3NpdGlvbiI6MCwiZG9jX3Bvc2l0aW9uIjowLCJkb2NfaWQiOiJmOGNhNjcxZmFhYTMxN2ZiLTAxN2U3ZjgxZjViOTQ1N2EifQ%3D%3Dinline_doc_idf8ca671faaa317fb-017e7f81f5b9457a)[ { → 入栈- 遇到右括号- 栈空 → 无匹配左括号 → false- 栈顶不匹配 → false- 匹配 → 出栈4. 遍历结束栈必须为空才算全部匹配成功四、代码实现Pythonpythondef isValid(s: str) - bool:# 奇数长度直接返回if len(s) % 2 ! 0:return Falsestack []# 右括号 → 对应左括号 的映射mapping {): (, ]: [, }: {}for c in s:# 右括号if c in mapping:# 栈空 或 不匹配if not stack or stack[-1] ! mapping[c]:return Falsestack.pop()# 左括号else:stack.append(c)# 最终栈必须为空return len(stack) 0五、复杂度分析- 时间复杂度O(n)每个字符只遍历一次入栈出栈都是 O(1)- 空间复杂度O(n)最坏情况全是左括号栈存全部字符