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

标签: 贪心 数组 字符串 动态规划

难度: Medium

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 <= 105
  • 1 <= neededTime[i] <= 104
  • colors 仅由小写英文字母组成

Submission

运行时间: 107 ms

内存: 24.4 MB

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        cur=neededTime[0]
        n=len(neededTime)
        ans=0
        for r in range(1,n):
            v=neededTime[r]
            if colors[r]==colors[r-1]:
                if cur<v:
                    ans+=cur
                    cur=v
                else:
                    ans+=v
            else:
                cur=neededTime[r]
        return ans

Explain

本题解的核心思想是贪心算法。为了让绳子上的气球颜色不连续，我们需要从连续的相同颜色的气球组中移除一些气球。具体策略是，在每个连续相同颜色的气球序列中，保留移除成本最高的气球，移除其他的气球。这样，我们可以确保移除成本总和最小。解法通过一次遍历实现，使用一个变量`cur`来记录当前连续颜色序列中成本最高的气球的移除时间，以及一个变量`ans`来累加需要移除的气球的总时间。每次遇到相同颜色的气球时，比较当前气球的移除时间和`cur`，并更新`cur`及`ans`。当颜色变化时，重置`cur`为当前气球的移除时间。

时间复杂度: O(n)

空间复杂度: O(1)

    class Solution:
        def minCost(self, colors: str, neededTime: List[int]) -> int:
            cur = neededTime[0]  # 初始化cur为第一个气球的移除时间
            n = len(neededTime)  # 总气球数量
            ans = 0  # 初始化总移除成本为0
            for r in range(1, n):  # 从第二个气球开始遍历
                v = neededTime[r]  # 当前气球的移除时间
                if colors[r] == colors[r-1]:  # 如果当前气球与前一个气球颜色相同
                    if cur < v:  # 如果之前记录的成本小于当前气球的成本
                        ans += cur  # 增加较小成本到总成本
                        cur = v  # 更新cur为较大成本
                    else:  # 如果之前记录的成本大于等于当前气球的成本
                        ans += v  # 增加当前成本到总成本
                else:  # 如果当前气球与前一个气球颜色不同
                    cur = v  # 更新cur为当前气球的移除时间
            return ans  # 返回总移除成本

Explore

在贪心算法中，选择保留成本最高的气球并移除其他的气球的策略是基于最小化移除成本的考虑。当需要打断一个连续的颜色序列时，如果保留成本最低的气球，则需要移除其余所有气球，这会导致较高的总成本。相反，如果保留成本最高的气球，那么移除的气球成本之和将是最小的，从而总的移除成本也是最低的。这种方法通过每次只保留单个最高成本的气球，并移除所有其他较低成本的气球，确保了每次操作都是局部最优的，从而实现全局的最小成本。

在代码实现中，当遇到两个连续的气球颜色相同且移除成本相同的情况时，算法会将第一个气球的成本加入到总成本中，并更新`cur`为第二个气球的成本。这样做的理由是，由于成本相同，选择移除哪一个气球对总成本的影响是一样的。因此，算法简单地选择移除先遇到的气球，并继续比较后续气球。

是的，这种方法在处理只有一个颜色的气球序列时也能正确输出结果。在给定的例子中，气球颜色都相同，算法会通过比较连续气球的移除成本来选择保留成本最大的气球。在这个过程中，它会逐步添加较小的成本到总成本中。对于示例中的序列，算法会最终保留成本为5的气球，并将1, 2, 3, 4的成本加到总成本中，总成本为10，这是正确的结果。

如果`colors`为空或`neededTime`为空，则在执行代码时会遇到问题。因为代码中没有检查`colors`或`neededTime`的长度，直接初始化`cur`为`neededTime[0]`，这会在空列表上引发索引错误。为了让代码更健壮，应添加对`colors`和`neededTime`非空的检查。如果它们为空，应该返回0，因为没有气球需要移除。