题目描述
思路解析动画文字版
记牢这句:分高的那对先用一遍栈删光,剩下的串再用一遍栈删另一对,两遍得分相加。下面每一帧都在套它。
看舞台。上面一排是要扫的字符串 "abbaab",下面这根竖栈一会儿会把暂时删不掉的字符摞起来。因为 "ba" 值 5 分、"ab" 值 4 分,我们定下计划:第一遍只盯着删 "ba",第二遍再回收 "ab"。指针还没出发,栈是空的,总分 0。
第一遍正式开始。这一遍眼里只有高分对 "ba"。规则很简单:栈顶是 "b"、当前字符是 "a",就说明它俩贴在一起能凑成 "ba",弹掉栈顶那个 "b"、和当前的 "a" 一起消掉,加 5 分;凑不成就把当前字符压进栈,留着以后看。
指针走到第 0 位,是 "a"。现在栈顶是 空的。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
凑不成 "ba"(栈本来是空的),所以把 "a" 压进栈,先存着。总分还是 0。
指针走到第 1 位,是 "b"。现在栈顶是 "a"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 0。
指针走到第 2 位,是 "b"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 0。
指针走到第 3 位,是 "a"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
栈顶 "b" 配上当前 "a",正好是一个 "ba",消掉这一对,加 5 分,总分变成 5。栈顶那个 "b" 被弹走,栈矮了一层。
指针走到第 4 位,是 "a"。现在栈顶是 "b"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "a" 压进栈。
栈顶 "b" 配上当前 "a",正好是一个 "ba",消掉这一对,加 5 分,总分变成 10。栈顶那个 "b" 被弹走,栈矮了一层。
指针走到第 5 位,是 "b"。现在栈顶是 "a"。判一下:栈顶是不是 "b"、当前是不是 "a",凑得成 "ba" 就消、加分,凑不成就把 "b" 压进栈。
凑不成 "ba"(栈顶不是 "b" 或当前不是 "a"),所以把 "b" 压进栈,先存着。总分还是 10。
第一遍扫到头了。一路上凑成了 2 个 "ba",每个 5 分,拿下 10 分。栈里现在剩 "ab",这就是删光所有 "ba" 之后删不动的残串。接下来把这段残串拿去做第二遍。
第二遍开始。舞台上排换成了第一遍剩下的 "ab"。这一遍改盯低分对 "ab":栈顶是 "a"、当前是 "b",就凑成 "ab" 消掉、加 4 分,凑不成就压栈。总分接着第一遍的 10 往上加。
指针看残串第 0 位,是 "a"。栈顶是 空的。判一下能不能凑成 "ab":要栈顶是 "a"、当前是 "b"。
凑不成 "ab",把 "a" 压进栈。总分还是 10。
指针看残串第 1 位,是 "b"。栈顶是 "a"。判一下能不能凑成 "ab":要栈顶是 "a"、当前是 "b"。
栈顶 "a" 配上当前 "b",凑成一个 "ab",消掉,加 4 分,总分变成 14。
第二遍也扫完了。在残串 "ab" 上凑成了 1 个 "ab",每个 4 分,又进账 4 分。栈现在空了,再也凑不出任何一对。总分停在 14。
回放一整局。从 "abbaab" 出发:第一遍贪心删掉 2 个高分对 "ba" 拿 10 分,残串 "ab";第二遍删掉 1 个低分对 "ab" 拿 4 分。10 加 4 等于 14,这就是最大得分。关键就在第一步定了「高分对先删」,顺序一对,分数自然到顶。
边界先想清:没有 b 时一分拿不到、单个高分对在第一遍结算、单个低分对留到第二遍结算。
面试重点:冲突点判给高分对证明贪心最优、计数法把两遍压成一遍 O(1)、认出抢资源的局部消除题就排收益贪心。
参考代码
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 maximumGain(self, s: str, x: int, y: int) -> int: a, b = "a", "b" if x < y: x, y = y, x a, b = b, a ans = cnt1 = cnt2 = 0 for c in s: if c == a: cnt1 += 1 elif c == b: if cnt1: ans += x cnt1 -= 1 else: cnt2 += 1 else: ans += min(cnt1, cnt2) * y cnt1 = cnt2 = 0 ans += min(cnt1, cnt2) * y return ans复杂度
- 时间：O(n)，n 是字符串长度。无论两遍栈还是一遍计数,每个字符只做常数次比较与加减,总共线性扫,合计 O(n)
- 空间：O(n) / O(1)，动画演示的两遍栈,栈最坏会摞住大半个串(比如全是 "aaaa"),峰值是 O(n);参考代码的计数法只用 cnt1、cnt2 两个整数,是 O(1)。看你用哪种实现。返回的总分不计入额外空间
易错点
面试追问把动画讲成自己的话
追问怎么证明高分对优先一定最优,而不是某些情况下先删低分对更好?
追问能不能不开两遍栈,一遍扫完就出答案?
追问这类题怎么认套路?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出游戏的获胜者
LeetCode 1823 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题