---

1578. 使绳子变成彩色的最短时间

• 标签：贪心、数组、字符串、动态规划
• 难度：中等

题目链接

• 1578. 使绳子变成彩色的最短时间 - 力扣

题目大意

描述：绳子由 $n$ 个气球组成，每个气球有颜色 $colors[i]$。每个气球的移除时间为 $neededTime[i]$。

要求：移除一些气球，使得绳子上没有相邻的相同颜色。返回最小的总移除时间。

说明：

• $1 \le colors.length \le 10^5$。
• $1 \le neededTime[i] \le 10^4$。

示例：

• 示例 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 不需要从绳子上移除任何气球。

解题思路

思路 1：贪心

1. 核心思想

对于每一段连续相同颜色的气球，只能保留其中一个（否则会有相邻同色）。为了总移除时间最少，保留移除时间最大的那个，移除其余所有。

2. 具体步骤

第 1 步：遍历 $colors$，找出连续相同颜色的段。

第 2 步：对于每个连续段，累加段内所有移除时间，减去段内最大移除时间。

第 3 步：返回总累加值。

3. 举例说明

以 $colors = "abaac", neededTime = [1,2,3,4,5]$ 为例：

• 连续段 a（位置 $0$）：单调，跳过。
• 连续段 b（位置 $1$）：单调，跳过。
• 连续段 aa（位置 $2,3$）：总和 $3+4=7$，最大 $4$，移除 $7-4=3$（移除时间 $3$ 的气球）。
• 连续段 c（位置 $4$）：单调，跳过。

总时间 $= 3$。

以 $colors = "aabaa", neededTime = [1,2,3,4,1]$ 为例：

• 连续段 aa（位置 $0,1$）：总和 $1+2=3$，最大 $2$，移除 $3-2=1$。
• 连续段 b（位置 $2$）：单调，跳过。
• 连续段 aa（位置 $3,4$）：总和 $4+1=5$，最大 $4$，移除 $5-4=1$。

总时间 $= 2$。

思路 1：代码

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(colors)
        ans = 0
        i = 0
        while i < n:
            j = i
            total = 0
            max_time = 0
            while j < n and colors[j] == colors[i]:
                total += neededTime[j]
                max_time = max(max_time, neededTime[j])
                j += 1
            if j - i > 1:  # 至少 2 个相邻相同
                ans += total - max_time
            i = j
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。