使绳子变成彩色的最短时间 图解题解

让相邻气球颜色不同，最少花多少删除时间

一排气球串成绳子，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 不显眼，换组数就少算一大截。另一个是把某段全删光：一段只需留一个就满足相邻不同，留最贵的省最多，全删等于白扔一份最大时间。还有人按「段长减一个最小值」凑，可代价算的是时间不是个数，写出来必须是段总和减段最大。

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_max

C++

#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;
    }
}