题目描述
思路解析动画文字版
记住这句:每段留最贵的、移其余,代价 = 段总和 减 段最大。下面每帧都在套它。
开局：第 0 个气球 红(3) 单独开一段（绿色），组内 sum=3、max=3，还没算移除代价。
看第 1 个 红(5)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 1 个 红(5) 并进当前段。组内 sum 累到 8，max 取到 5（先不结算，等这段结束再算）。
看第 2 个 蓝(10)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
颜色变了，上一段结算：段内留下最贵的 5（红框=保留），移掉其余，本段代价 8 减 5 = 3。新一段从第 2 个 蓝(10) 开始（绿色）。
看第 3 个 蓝(7)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 3 个 蓝(7) 并进当前段。组内 sum 累到 17，max 取到 10（先不结算，等这段结束再算）。
看第 4 个 蓝(5)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 4 个 蓝(5) 并进当前段。组内 sum 累到 22，max 取到 10（先不结算，等这段结束再算）。
看第 5 个 红(3)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色变了，上一段结算：段内留下最贵的 10（红框=保留），移掉其余，本段代价 22 减 10 = 12。新一段从第 5 个 红(3) 开始（绿色）。
看第 6 个 蓝(5)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
颜色变了，上一段结算：段内留下最贵的 3（红框=保留），移掉其余，本段代价 3 减 3 = 0。新一段从第 6 个 蓝(5) 开始（绿色）。
看第 7 个 蓝(5)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 7 个 蓝(5) 并进当前段。组内 sum 累到 10，max 取到 5（先不结算，等这段结束再算）。
看第 8 个 蓝(4)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 8 个 蓝(4) 并进当前段。组内 sum 累到 14，max 取到 5（先不结算，等这段结束再算）。
看第 9 个 蓝(8)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
颜色相同，第 9 个 蓝(8) 并进当前段。组内 sum 累到 22，max 取到 8（先不结算，等这段结束再算）。
扫到末尾，把最后一段也结算：留下最贵的 8（红框），代价 22 减 8 = 14。
全程结束：每段绿色那个是保留的（共 4 段、4 个气球留下），灰色都被移除。各段代价相加 = 29，这就是答案。
边界先想清：单个为 0、本就交替为 0、全同色就是总和减最大。
两个高频追问：约束变化如何改分组键，以及边扫边结算的等价写法。
参考代码
from typing import Listclass Solution: def minCost(self, colors: str, neededTime: List[int]) -> int: ans = group_sum = group_max = 0 prev = '' for c, t in zip(colors, neededTime): if c != prev: ans += group_sum - group_max group_sum = group_max = 0 prev = c group_sum += t group_max = max(group_max, t) return ans + group_sum - group_max复杂度
- 时间：O(n)，从头到尾扫一遍气球
- 空间：O(1)，只用 sum、max、ans 三个变量
易错点
面试追问把动画讲成自己的话
追问如果允许相邻同色、改成要求「整条绳子颜色全不同」呢？
追问能不能不显式分组，用「和前一个比较」的写法实现？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符频次唯一的最小删除次数
LeetCode 1647 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题