题目描述
思路解析
一句话答案：LeetCode 1578 让字符串多彩的最少时间：相邻同色气球只能留一个，把连续同色切成一段段，每段留删除代价最大的、其余代价累加，段总和减段最大就是这段开销，时间 O(n)、空间 O(1)。
让相邻气球颜色不同，最少花多少删除时间
一排气球串成绳子，colors 记每个气球的颜色，neededTime[i] 是删掉第 i 个气球要花的时间。允许删掉任意几个，只要剩下的相邻颜色都不同就行，问最少花多少时间。题面例子 colors="abaac"、neededTime=[1,2,3,4,5]，答案是 3。碍事的只有连续同色的气球，本来交替的不用动。
同色连成一串，到底删到只剩谁
一段连续同色里相邻颜色全相同、都算违规，这段最后只能留一个、其余全删。为难的是留哪个：留下的不花钱，被删的每个都按 neededTime 付时间。要挨个试「保留第几个、删其余」再比总花费，一段长 k 就得试 k 种，几段叠起来白算几遍。
为什么每段都留最贵的那个最省
既然一段里非留一个不可，那留谁、删谁只看怎么最省。被删的时间要全付，留下的不付，想让总付出最小，就把时间最大的那个留下当免死金牌、其余删掉。于是这段开销正好等于段内所有时间之和，减去段内最大的那个。
段与段之间：这段留谁管不着隔壁那段，两段的账各算各的。每段各取本段最省，拼起来就是整条绳子最省，这就是贪心在这题里的样子：按连续同色段切开、逐段独立结算。
一趟扫过去，边走边把每段结清
不必真把每段切出来存着。备三个累加器：ans 记已结清总开销，group_sum 记当前段时间之和，group_max 记当前段最大时间。从左往右扫每个气球跟前一个比颜色：变了就先结清上一段（ans 加 group_sum 减 group_max），再把两者清零开新段；同色就把当前时间累进 group_sum，并更新 group_max。
收尾最容易漏：循环走完，最后一段身后没有下一个不同颜色触发结算，得在返回前再补结一次。整条绳子只扫一遍，时间 O(n)；全程只用三个变量，空间 O(1)。
abaac、[1,2,3,4,5] 亲手结一遍
开头 a(1) 开一段，group_sum=1、group_max=1。第二个 b(2) 变色，先结上一段：加 1 减 1 得 0，ans 还是 0；新段 group_sum=2、group_max=2。第三个 a(3) 又变色，结算加 2 减 2 得 0，ans 仍是 0；新段 group_sum=3、group_max=3。
第四个还是 a(4)，同色累加：group_sum=3+4=7，group_max=max(3,4)=4。第五个 c(5) 变色，把这段 aa 结掉：加 7 减 4 得 3，ans=3；新段 group_sum=5、group_max=5。扫到末尾补结最后一段 c：加 5 减 5 得 0。ans 停在 3，只需删掉那段 aa 里较便宜的 a(3)，正好花 3。
常把开销算歪的几个错法
最常撞的是循环结束忘了补结最后一段：末段没人触发结算，开销就从答案里蒸发，样例末段 c 恰好是 0 不显眼，换组数就少算一大截。另一个是把某段全删光：一段只需留一个就满足相邻不同，留最贵的省最多，全删等于白扔一份最大时间。还有人按「段长减一个最小值」凑，可代价算的是时间不是个数，写出来必须是段总和减段最大。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句:每段留最贵的、移其余,代价 = 段总和 减 段最大。下面每帧都在套它。
开局：第 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 1630 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题