LeetCode 20. 有效的括号从栈的基础到括号匹配这道题本身不难但很适合用来重新理解“栈”到底是干什么的。一开始我只是知道左括号出现 → 先保存右括号出现 → 看前面有没有对应的左括号不过细想之后可以发现这里的关键应该是右括号要匹配的一直都是最近一个还没有被匹配掉的左括号。而 这种 “最后放进去的东西最先被拿出来”正好就是栈的特点。题目链接leetcode 20弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化文章目录LeetCode 20. 有效的括号从栈的基础到括号匹配题目回顾一、先重新认识一下栈Python 里怎么使用栈1. 入栈2. 查看栈顶3. 出栈4. 判断栈是否为空二、为什么括号匹配会想到栈三、我的第一版思路左括号入栈右括号分别判断四、第一个问题如果右括号出现时栈是空的怎么办五、第一版代码六、能不能把三套判断合成一套七、左括号的判断也可以缩短八、最终优化后的代码九、复杂度十、最后把整个思路串起来题目回顾题目给出一个只包含( ) [ ] { }的字符串需要判断其中的括号是否能够正确匹配。例如()[]{}每个左括号都能找到正确的右括号所以返回True而([)]虽然三种括号的数量看起来没有问题但匹配顺序是错误的所以返回False因此这道题不只是判断左括号数量 右括号数量还必须判断括号出现的顺序是否正确。一、先重新认识一下栈栈Stack最核心的特点只有一句话后进先出 ( Last In First Out )可以把它想成一摞盘子最后放进去的盘子 ↓ 最先拿出来例如, 依次放入1 → 2 → 3那么取出的顺序就是3 → 2 → 1Python 里怎么使用栈LeetCode 中通常不需要专门创建一个 Stack 类直接使用list就可以。stack[]最常用的操作只有几个。1. 入栈stack.append(x)例如stack[]stack.append(()stack.append([)现在[(, [] ↑ 栈顶2. 查看栈顶stack[-1]它只查看最后一个元素不会删除。例如stack[(,[]stack[-1]得到[3. 出栈stack.pop()会把栈顶元素删除。例如stack[(,[]stack.pop()之后也就变成[(]也可以:stack[(,[]xstack.pop()x[把最后一个元素取出, 并且删除4. 判断栈是否为空Python 中列表可以直接参与布尔判断ifstack:表示判断 stack 是否为非空列表stack 里至少还有一个元素 → True而ifnotstack:表示stack 是否为空列表所以普通栈最需要记住的就是append() → 入栈 stack[-1] → 看栈顶 pop() → 弹出栈顶 if not stack → 判断是不是空栈二、为什么括号匹配会想到栈题目中有三组括号() [] {}例如([{}])从左往右看。先遇到(暂时不知道它什么时候闭合所以先保存。然后[也先保存。然后{继续保存。这时候栈里是[(, [, {] ↑ 栈顶接下来遇到}它应该和谁匹配不是最早出现的(也不是[而是最近出现、还没有被处理的{于是{ ↓ 和 } 匹配 ↓ pop接下来]→ 再和现在的栈顶[匹配。最后)和(匹配。所以整个过程就是遇到左括号 → 入栈 遇到右括号 → 和栈顶比较 匹配 → 栈顶出栈 不匹配 → False这里还有一个容易想到的方法能不能只统计左括号和右括号的数量例如([)]里面(和)各有一个[和]也各有一个数量完全对得上。但是它仍然是错误的因为真正的匹配过程是( ↓ [ ↓ 此时遇到 )) 最近面对的左括号其实是[而不是(所以括号匹配不仅要看“数量”还要看最近一个还没有匹配的左括号是谁这就是为什么这里特别适合用栈。三、我的第一版思路左括号入栈右括号分别判断最开始可以很自然地写成ifcurrent(orcurrent[orcurrent{:stack.append(current)如果遇到右括号再分别判断ifcurrent):ifstack[-1](:stack.pop()另外两种同理。思路本身没问题左括号 → 保存 右括号 → 检查栈顶 对应 → pop 不对应 → False但是这里很快会出现一个漏洞。四、第一个问题如果右括号出现时栈是空的怎么办例如){第一个字符就是)这时候stack[]如果直接执行stack[-1]就会报错。因为空列表根本没有最后一个元素。所以在查看stack[-1]之前必须先判断ifnotstack:returnFalse这个逻辑其实也很好理解出现右括号 ↓ 前面却没有任何左括号 ↓ 不可能匹配 ↓ False所以栈题里有一个很常见的小习惯使用stack[-1]或stack.pop()之前先想一下栈有没有可能为空。五、第一版代码修正之后第一版代码就已经可以做出来classSolution:defisValid(self,s:str)-bool:stack[]# 长度是奇数,肯定会有不匹配的iflen(s)%2!0:returnFalseforcurrentins:ifcurrent(orcurrent[orcurrent{:stack.append(current)continueifnotstack:returnFalsetopstack[-1]ifcurrent):iftop(:stack.pop()continuereturnFalseifcurrent]:iftop[:stack.pop()continuereturnFalseifcurrent}:iftop{:stack.pop()continuereturnFalsereturnnotstack这个版本逻辑已经完整了。结尾为什么是这样判断的其实return not stack展开就是:ifstack:returnFalseelse:returnTrue这里是在判断所有字符都遍历完之后栈里还有没有没被匹配掉的左括号。因为stack 不为空 → 还有左括号剩在栈里 → 说明没有全部匹配 → False例如(()最后可能剩下stack[(]所以返回False。而如果stack 为空 → 所有左括号都已经被对应的右括号弹出了 → 匹配完成 → True所以这段其实可以直接简化成returnnotstack因为stack 为空 → not stack True stack 不为空 → not stack False六、能不能把三套判断合成一套写完以后会发现一个问题) → 检查 ( ] → 检查 [ } → 检查 {三段代码其实是在重复做同一件事。而三种右括号实际上都有固定对应关系) → ( ] → [ } → {既然如此那么与其写三套几乎一样的if不如先把这组固定的对应关系保存下来需要的时候直接查:match{):(,]:[,}:{}一个东西 → 对应另一个东西非常适合用字典。这里key → 右括号 value → 它应该对应的左括号例如match[)]得到(而match[]]得到[所以原来三套如果是 ) → 看栈顶是不是 ( ....现在可以统一成ifstack[-1]!match[current]:returnFalse也就是当前右括号 ↓ 通过字典查到它应该对应的左括号 ↓ 和栈顶比较七、左括号的判断也可以缩短原来ifcurrent(orcurrent[orcurrent{:其实 Python 可以直接判断ifcurrentin([{:因为([{本身就是一个字符串里面有三个字符( [ {所以currentin([{其实是在问current 是不是这三个字符之一例如(in([{得到True而]in([{得到False所以ifcurrentin([{:stack.append(current)就可以表示如果 current 是左括号 → 入栈八、最终优化后的代码classSolution:defisValid(self,s:str)-bool:stack[]match{):(,]:[,}:{}forcurrentins:# 左括号直接入栈ifcurrentin([{:stack.append(current)# 否则就是右括号else:# 没有左括号可以和它匹配ifnotstack:returnFalse# 栈顶和当前右括号不对应ifstack[-1]!match[current]:returnFalse# 匹配成功弹出栈顶stack.pop()# 最后栈必须为空returnnotstack九、复杂度整个字符串只遍历一次。每个括号最多入栈一次 出栈一次所以时间复杂度O(n)最坏情况下例如(((((((所有左括号都会进入栈。因此空间复杂度O(n)十、最后把整个思路串起来一开始先看题目左括号和右括号需要正确配对进一步发现右括号出现时 ↓ 要匹配最近一个还没有被处理的左括号而最近放进去 ↓ 最先拿出来正好就是栈所以左括号 → append 入栈 右括号 → 看 stack[-1] 对应 → pop 不对应 → False接下来发现一个漏洞右括号出现 stack 为空 ↓ 不能直接 stack[-1] ↓ return False再继续优化三组括号有固定对应关系 ↓ 用 dict 保存 ) → ( ] → [ } → {于是三套判断分别写 if可以变成stack[-1]match[current]最终整道题就可以记成遍历当前括号 ↓ 是左括号 ├─ 是 → append 入栈 → 继续 │ └─ 否 → 说明是右括号 ↓ 栈为空 ├─ 是 → False │ └─ 否 ↓ 栈顶是否匹配 ├─ 否 → False │ └─ 是 → pop ↓ 继续遍历 遍历结束 ↓ 栈为空 ├─ 是 → True └─ 否 → False最后, 我觉得, 这道题值得记住的是当一个问题需要“优先处理最近出现、还没有被处理的东西”时可以考虑栈。