题目描述
思路解析动画文字版
记牢「左括号压 0 开新层、右括号结算栈顶(空层得 1、否则翻倍)、把分数加回外层」,下面每一帧都在套它。
准备 · 栈底压入一个 0：开始之前,先在栈底放一个 0。这个 0 代表「最外面一层」当前的累计分数,所有算出来的分最终都会汇总到它身上。上方一排是要依次处理的 8 个括号,我们从最左边开始,一个一个扫。
读第 1 个 · 左括号 (：扫到第 1 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
开新层 · 压入 0：压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
读第 2 个 · 左括号 (：扫到第 2 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
开新层 · 压入 0：压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
读第 3 个 · 右括号 )：扫到第 3 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
弹出 · 这层累计 0：把栈顶弹出来,这层封口前累计的分数是 v = 0。它是 0,意味着这一层从压进来到现在什么分都没加过,也就是一对紧挨着的空括号 ()。
结算 · 这层得 1：v 是 0,说明这就是一对空括号 (),按规则 () 得 1 分。把这 1 分加到新的栈顶,也就是它外面那一层。外层分数从此多了 1。
读第 4 个 · 左括号 (：扫到第 4 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
开新层 · 压入 0：压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
读第 5 个 · 左括号 (：扫到第 5 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
开新层 · 压入 0：压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
读第 6 个 · 右括号 )：扫到第 6 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
弹出 · 这层累计 0：把栈顶弹出来,这层封口前累计的分数是 v = 0。它是 0,意味着这一层从压进来到现在什么分都没加过,也就是一对紧挨着的空括号 ()。
结算 · 这层得 1：v 是 0,说明这就是一对空括号 (),按规则 () 得 1 分。把这 1 分加到新的栈顶,也就是它外面那一层。外层分数从此多了 1。
读第 7 个 · 右括号 )：扫到第 7 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
弹出 · 这层累计 1：把栈顶弹出来,这层封口前累计的分数是 v = 1。它大于 0,意味着这一层里面已经包着别的括号、攒了 1 分。
结算 · 这层翻倍得 2：v 是 1 不为 0,说明里面包着东西,按规则 (A) 要翻倍:2 乘 1 等于 2。把 2 加到新的栈顶,也就是外面那一层。外层分数从此多了 2。
读第 8 个 · 右括号 )：扫到第 8 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
弹出 · 这层累计 3：把栈顶弹出来,这层封口前累计的分数是 v = 3。它大于 0,意味着这一层里面已经包着别的括号、攒了 3 分。
结算 · 这层翻倍得 6：v 是 3 不为 0,说明里面包着东西,按规则 (A) 要翻倍:2 乘 3 等于 6。把 6 加到新的栈顶,也就是外面那一层。外层分数从此多了 6。
扫描结束 · 总分 6：8 个括号全部处理完,栈里只剩栈底这一个数 6。它就是最外层汇总到的全部分数,也就是整串的总分。把过程连起来看:最里面两对 () 各得 1,被层层括号包着不断翻倍累加,最终汇成 6。
边界先想清:单对得 1、并排相加、嵌套翻倍,三种基本形态拼出所有答案。
面试重点:深度计数法 O(1) 空间是优化解;栈底放 0 是给最外层留累加的地基。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def scoreOfParentheses(self, s: str) -> int: ans = d = 0 for i, c in enumerate(s): if c == '(': d += 1 else: d -= 1 if s[i - 1] == '(': ans += 1 << d return ans复杂度
- 时间：O(n)，n 为括号个数,从左到右只扫一遍,每个字符做常数次操作
- 空间：O(n) / O(1)，动画的分数栈最坏存 O(n) 层;参考代码的深度计数法只用一个变量 d,空间 O(1)
易错点
面试追问把动画讲成自己的话
追问除了用栈,还有更省空间的写法吗?
追问为什么分数栈的栈底要先放一个 0?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
股票价格跨度
LeetCode 901 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题