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 <= 10^5
  • 1 <= neededTime[i] <= 10^4
  • colors 仅含小写英文字母

解题思路

解题思路

这道题的核心思想是：对于每一组连续相同颜色的气球，我们需要保留其中移除时间最长的那个，移除其余所有气球。

贪心策略分析

当遇到连续相同颜色的气球时，为了使总移除时间最小，我们应该：

  1. 保留这组气球中移除时间最长的那个
  2. 移除其他所有气球

这样做的原因是，我们必须移除 k-1 个气球（k 为连续相同颜色气球的数量），为了最小化移除时间，自然要保留移除时间最大的那个。

算法步骤

  1. 遍历字符串，当发现相邻气球颜色相同时，开始处理这一组连续相同的气球
  2. 对于每一组连续相同的气球，计算总时间和最大时间
  3. 将 总时间 - 最大时间 加入到结果中
  4. 继续处理下一组

这种贪心策略是最优的，因为我们总是在每个连续组内做出最优选择。

推荐解法：贪心算法 - 时间复杂度 O(n)，空间复杂度 O(1)

代码实现

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int result = 0;
        int i = 0;
        int n = colors.length();
        
        while (i < n) {
            if (i < n - 1 && colors[i] == colors[i + 1]) {
                int sum = 0;
                int maxTime = 0;
                
                while (i < n - 1 && colors[i] == colors[i + 1]) {
                    sum += neededTime[i];
                    maxTime = max(maxTime, neededTime[i]);
                    i++;
                }
                sum += neededTime[i];
                maxTime = max(maxTime, neededTime[i]);
                
                result += sum - maxTime;
            }
            i++;
        }
        
        return result;
    }
};

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        result = 0
        i = 0
        n = len(colors)
        
        while i < n:
            if i < n - 1 and colors[i] == colors[i + 1]:
                sum_time = 0
                max_time = 0
                
                while i < n - 1 and colors[i] == colors[i + 1]:
                    sum_time += neededTime[i]
                    max_time = max(max_time, neededTime[i])
                    i += 1
                
                sum_time += neededTime[i]
                max_time = max(max_time, neededTime[i])
                
                result += sum_time - max_time
            
            i += 1
        
        return result

public class Solution {
    public int MinCost(string colors, int[] neededTime) {
        int result = 0;
        int i = 0;
        int n = colors.Length;
        
        while (i < n) {
            if (i < n - 1 && colors[i] == colors[i + 1]) {
                int sum = 0;
                int maxTime = 0;
                
                while (i < n - 1 && colors[i] == colors[i + 1]) {
                    sum += neededTime[i];
                    maxTime = Math.Max(maxTime, neededTime[i]);
                    i++;
                }
                sum += neededTime[i];
                maxTime = Math.Max(maxTime, neededTime[i]);
                
                result += sum - maxTime;
            }
            i++;
        }
        
        return result;
    }
}

var minCost = function(colors, neededTime) {
    let result = 0;
    let i = 0;
    const n = colors.length;
    
    while (i < n) {
        if (i < n - 1 && colors[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小说明
时间复杂度O(n)只需要遍历一次字符串，每个元素最多被访问两次
空间复杂度O(1)只使用了常数个变量来存储中间结果