LeetCode 1578中等贪心
使绳子变成彩色的最短时间 图解题解
这道题到底在问什么
给定颜色串 colors 和等长数组 neededTime，neededTime[i] 是移除第 i 个气球的代价。移除若干气球，使最终相邻气球颜色互不相同，返回最小总代价。
- 输入
- colors="abaac", time=[1,2,3,4,5]
- 输出
- 3 （连续 aa 里移掉较小的 3）
- 输入
- colors="abc", time=[1,2,3]
- 输出
- 0 （本来就相邻不同，无需移除）
最优解：一步一步想明白
- 3记住这句:每段留最贵的、移其余,代价 = 段总和 减 段最大。下面每帧都在套它。
- 4开局：第 0 个气球 红(3) 单独开一段（绿色），组内 sum=3、max=3，还没算移除代价。
- 5看第 1 个 红(5)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
- 6颜色相同，第 1 个 红(5) 并进当前段。组内 sum 累到 8，max 取到 5（先不结算，等这段结束再算）。
- 7看第 2 个 蓝(10)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
- 8颜色变了，上一段结算：段内留下最贵的 5（红框=保留），移掉其余，本段代价 8 减 5 = 3。新一段从第 2 个 蓝(10) 开始（绿色）。
- 9看第 3 个 蓝(7)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 10颜色相同，第 3 个 蓝(7) 并进当前段。组内 sum 累到 17，max 取到 10（先不结算，等这段结束再算）。
- 11看第 4 个 蓝(5)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 12颜色相同，第 4 个 蓝(5) 并进当前段。组内 sum 累到 22，max 取到 10（先不结算，等这段结束再算）。
- 13看第 5 个 红(3)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 14颜色变了，上一段结算：段内留下最贵的 10（红框=保留），移掉其余，本段代价 22 减 10 = 12。新一段从第 5 个 红(3) 开始（绿色）。
- 15看第 6 个 蓝(5)，和前一个 红 比颜色。绿色是当前正在生长的同色段。
- 16颜色变了，上一段结算：段内留下最贵的 3（红框=保留），移掉其余，本段代价 3 减 3 = 0。新一段从第 6 个 蓝(5) 开始（绿色）。
- 17看第 7 个 蓝(5)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 18颜色相同，第 7 个 蓝(5) 并进当前段。组内 sum 累到 10，max 取到 5（先不结算，等这段结束再算）。
- 19看第 8 个 蓝(4)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 20颜色相同，第 8 个 蓝(4) 并进当前段。组内 sum 累到 14，max 取到 5（先不结算，等这段结束再算）。
- 21看第 9 个 蓝(8)，和前一个 蓝 比颜色。绿色是当前正在生长的同色段。
- 22颜色相同，第 9 个 蓝(8) 并进当前段。组内 sum 累到 22，max 取到 8（先不结算，等这段结束再算）。
- 23扫到末尾，把最后一段也结算：留下最贵的 8（红框），代价 22 减 8 = 14。
- 24全程结束：每段绿色那个是保留的（共 4 段、4 个气球留下），灰色都被移除。各段代价相加 = 29，这就是答案。
⚠️ 容易写错的地方
✗ 错：每段把所有气球都移掉
✓ 对：每段留下最贵的那个、移其余
段内只需让相邻不同，留 1 个即可，留最贵的最省
✗ 错：循环结束忘了结算最后一段
✓ 对：出循环后再补一次 ans += sum 减 max
最后一段没有「下一个不同颜色」来触发结算，会漏掉
✗ 错：用「段长 减 1 个最小」去算
✓ 对：应是「段总和 减 段最大」
代价是时间不是个数，移掉的恰好是除最大外的全部，和等于总和减最大
完整代码（Python / C++ / Java）
Python
from typing import List
class 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_maxC++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int minCost(string colors, vector<int>& neededTime) {
int ans = 0, sum = 0, mx = 0;
char prev = 0;
for (int i = 0; i < (int)colors.size(); ++i) {
if (colors[i] != prev) {
ans += sum - mx;
sum = mx = 0;
prev = colors[i];
}
sum += neededTime[i];
mx = max(mx, neededTime[i]);
}
return ans + sum - mx;
}
};Java
import java.util.*;
class Solution {
public int minCost(String colors, int[] neededTime) {
int ans = 0, sum = 0, max = 0;
char prev = 0;
for (int i = 0; i < colors.length(); i++) {
if (colors.charAt(i) != prev) {
ans += sum - max;
sum = max = 0;
prev = colors.charAt(i);
}
sum += neededTime[i];
max = Math.max(max, neededTime[i]);
}
return ans + sum - max;
}
}复杂度
时间
O(n)
从头到尾扫一遍气球
空间
O(1)
只用 sum、max、ans 三个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使绳子变成彩色的最短时间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果允许相邻同色、改成要求「整条绳子颜色全不同」呢？+
那就不是分段贪心了：会变成每种颜色最多留 1 个的问题，需要按颜色聚合、对每种颜色留最大时间、移除其余，思路类似但分组键从「连续段」变成「颜色本身」。本题只要求相邻不同，所以只看连续段。
能不能不显式分组，用「和前一个比较」的写法实现？+
可以，也是更常见的写法：维护当前段的 sum 和 max，遇到与前一个不同的颜色就先把上一段结算（ans += sum 减 max）再重置，同色就累加。本题三语言参考代码用的就是这种「不显式存段、边扫边结算」的方式。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使绳子变成彩色的最短时间 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。