目标
Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。
Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。
返回 Bob 使绳子变成 彩色 需要的 最少时间 。
示例 1：
输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。示例 2：
输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。示例 3：
输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。说明：
- n == colors.length == neededTime.length
- 1 <= n <= 10^5
- 1 <= neededTime[i] <= 10^4
- colors 仅由小写英文字母组成
思路
水平的绳子上绑着一排气球，现在要使相邻的气球颜色不同，需要解开一些气球，解开每个气球的时间为 neededTime[i] 求所需的最短时间。
将相邻的颜色相同的气球放入堆中，仅保留耗时最大的即可。
代码
/**
* @date 2025-11-03 8:56
*/
public class MinCost1578 {
public int minCost(String colors, int[] neededTime) {
int n = neededTime.length;
int i = 0;
int res = 0;
while (i < n) {
int max = i;
int sum = 0;
char c = colors.charAt(i);
while (i < n && c == colors.charAt(i)) {
if (neededTime[i] > neededTime[max]) {
max = i;
}
sum += neededTime[i++];
}
res += sum - neededTime[max];
}
return res;
}
}
性能
