题目描述
思路解析动画文字版
记牢「数字入栈、加号压两数之和、D 压翻倍、C 弹栈、最后求和」,下面每一帧都在套它。
总览 · 把 8 个操作排成一排：上方一排是要依次处理的 8 个操作。栈一开始是空的,我们从最左边第一个操作开始,一个一个地按规则维护这个「有效得分栈」。请盯住栈顶,后面三种指令都只在栈顶附近动手。
读第 0 个 · 数字 5：扫到第 0 个操作,是个整数 5。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
数字入栈 · 5：把 5 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 5。继续往后扫第 一 个操作。
读第 1 个 · 数字 -2：扫到第 1 个操作,是个整数 -2。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
数字入栈 · -2：把 -2 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 -2。继续往后扫第 二 个操作。
读第 2 个 · 数字 4：扫到第 2 个操作,是个整数 4。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
数字入栈 · 4：把 4 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 4。继续往后扫第 三 个操作。
读第 3 个 · C：扫到第 3 个操作,是 "C"。它的含义是「把前一次得分作废、从记录里移除」。前一次得分就是栈顶的 4,接下来要把它弹出去。
C 结算 · 移除 4：把栈顶的 4 弹出栈,它从此不参与最后的求和。弹完之后,栈顶回到了它下面那个数,后续的指令都以这个新栈顶为「上一次得分」。
读第 4 个 · D：扫到第 4 个操作,是 "D"。它的含义是「本次得分等于前一次得分的两倍」。前一次得分就是栈顶的 -2,把它翻倍就是新得分。
D 结算 · 压入 -4：-2 乘 2 等于 -4,把这个新得分 -4 压进栈。原来的 -2 不受影响,它还是有效得分。栈顶现在变成了 -4。
读第 5 个 · 数字 9：扫到第 5 个操作,是个整数 9。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
数字入栈 · 9：把 9 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 9。继续往后扫第 六 个操作。
读第 6 个 · 加号：扫到第 6 个操作,是 "+"。它的含义是「本次得分等于前两次得分之和」。前两次得分就是栈顶的两个数:最上面是 9,往下一个是 -4。把它们加起来就是新得分。
加号结算 · 压入 5：9 加 -4 等于 5,把这个新得分 5 压进栈。注意原来的 9 和 -4 都还在,它们仍是有效得分,只是上面又多压了一个 5。继续看下一个操作。
读第 7 个 · 加号：扫到第 7 个操作,是 "+"。它的含义是「本次得分等于前两次得分之和」。前两次得分就是栈顶的两个数:最上面是 5,往下一个是 9。把它们加起来就是新得分。
加号结算 · 压入 14：5 加 9 等于 14,把这个新得分 14 压进栈。注意原来的 5 和 9 都还在,它们仍是有效得分,只是上面又多压了一个 14。继续看下一个操作。
扫描结束 · 栈中 6 个得分：8 个操作全部处理完,栈里现在剩下 5、-2、-4、9、5、14 这 6 个有效得分。被 "C" 作废的那个 4 早就弹掉了,不在里面。最后一步,把栈里这些数全加起来就是答案。
求和 · 已累计 5：从左往右把栈里的得分依次加起来。加上第 0 个 5 之后,running 从 0 变成 5。继续加下一个。
求和 · 已累计 3：从左往右把栈里的得分依次加起来。加上第 1 个 -2 之后,running 从 5 变成 3。继续加下一个。
求和 · 已累计 -1：从左往右把栈里的得分依次加起来。加上第 2 个 -4 之后,running 从 3 变成 -1。继续加下一个。
求和 · 已累计 8：从左往右把栈里的得分依次加起来。加上第 3 个 9 之后,running 从 -1 变成 8。继续加下一个。
求和 · 已累计 13：从左往右把栈里的得分依次加起来。加上第 4 个 5 之后,running 从 8 变成 13。继续加下一个。
求和 · 已累计 27：从左往右把栈里的得分依次加起来。加上第 5 个 14 之后,running 从 13 变成 27。全部加完,总和就是 27,这就是最终答案。
边界先想清:全被作废返回 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 calPoints(self, operations: List[str]) -> int: stk = [] for op in operations: if op == "+": stk.append(stk[-1] + stk[-2]) elif op == "D": stk.append(stk[-1] * 2) elif op == "C": stk.pop() else: stk.append(int(op)) return sum(stk)复杂度
- 时间：O(n)，n 为操作个数,每个操作只处理一次,末尾求和也是一遍
- 空间：O(n)，栈最多存下所有有效得分,规模是操作个数级别
易错点
面试追问把动画讲成自己的话
追问一定要用栈吗?能不能用普通数组?
追问如果操作里出现不合法的情况,比如对空记录用 "C",怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
比较含退格的字符串
LeetCode 844 · 简单 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题