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

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 仅由小写英文字母组成

方法一：贪心

思路与算法

根据题意可以知道，如果字符串 colors 中有若干相邻的重复颜色，则这些颜色中最多只能保留一个。因此，我们可以采取贪心的策略：在这一系列重复颜色中，我们保留删除成本最高的颜色，并删除其他颜色。这样得到的删除成本一定是最低的。

代码

[sol1-C++]

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int i = 0, len = colors.length();
        int ret = 0;
        while (i < len) {
            char ch = colors[i];
            int maxValue = 0;
            int sum = 0;

            while (i < len && colors[i] == ch) {
                maxValue = max(maxValue, neededTime[i]);
                sum += neededTime[i];
                i++;
            }
            ret += sum - maxValue;
        }
        return ret;
    }
};

[sol1-Java]

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int i = 0, len = colors.length();
        int ret = 0;
        while (i < len) {
            char ch = colors.charAt(i);
            int maxValue = 0;
            int sum = 0;

            while (i < len && colors.charAt(i) == ch) {
                maxValue = Math.max(maxValue, neededTime[i]);
                sum += neededTime[i];
                i++;
            }
            ret += sum - maxValue;
        }
        return ret;
    }
}

[sol1-C#]

public class Solution {
    public int MinCost(string colors, int[] neededTime) {
        int i = 0, len = colors.Length;
        int ret = 0;
        while (i < len) {
            char ch = colors[i];
            int maxValue = 0;
            int sum = 0;

            while (i < len && colors[i] == ch) {
                maxValue = Math.Max(maxValue, neededTime[i]);
                sum += neededTime[i];
                i++;
            }
            ret += sum - maxValue;
        }
        return ret;
    }
}

[sol1-Python3]

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        i = 0
        length = len(colors)
        ret = 0

        while i < length:
            ch = colors[i]
            maxValue = 0
            total = 0

            while i < length and colors[i] == ch:
                maxValue = max(maxValue, neededTime[i])
                total += neededTime[i]
                i += 1
            
            ret += total - maxValue
        
        return ret

[sol1-C]

int minCost(char* colors, int* neededTime, int neededTimeSize) {
    int i = 0;
    int ret = 0;
    while (i < neededTimeSize) {
        char ch = colors[i];
        int maxValue = 0;
        int sum = 0;

        while (i < neededTimeSize && colors[i] == ch) {
            maxValue = fmax(maxValue, neededTime[i]);
            sum += neededTime[i];
            i++;
        }
        ret += sum - maxValue;
    }
    return ret;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度。我们只需对字符串进行一次线性的扫描。

• 空间复杂度：O(1)。我们只开辟了常量大小的空间。