LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.03
• 题目：1578. 使绳子变成彩色的最短时间
• 难度：中等
• 标签: 贪心 数组 动态规划

1. 题目理解

问题描述：
Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

示例：

输入：colors = "abaac", neededTime = [1,2,3,4,5] 输出：3 解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。

核心诉求：移除连续相同颜色的气球，保证最终无连续重复颜色，且总移除时间最小。

2. 解题思路

核心观察

• 问题本质是「连续相同颜色的气球组中，仅保留 1 个，其余全部移除」，要使总时间最小，需保留组内「移除时间最大」的气球（移除其余耗时更小的，总耗时最优）。
• 无需一次性遍历整个连续组，通过「相邻气球对比」即可逐步筛选出组内最大耗时气球——连续相同组的最大耗时可通过两两对比迭代得到，不存在“连锁影响”。

算法步骤

1. 初始化变量：res 记录总最小移除时间（初始为 0），last 标记当前连续组中「待保留的气球索引」（初始为 0）。
2. 从第 1 个气球开始遍历（i=1）：
   • 若当前气球与 last 标记的气球颜色不同：更新 last 为当前索引 i，开启新的连续组。
   • 若颜色相同：比较两者的移除时间，累加耗时更小的那个到 res，并将 last 更新为耗时更大的气球索引（保留该气球）。
3. 遍历结束后，res 即为最小总移除时间。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public int minCost(String colors, int[] neededTime) {
        int res = 0;
        int last = 0;
        int i = 1;
        while (i < neededTime.length) {
            if (colors.charAt(i) == colors.charAt(last)) {
                if (neededTime[i] > neededTime[last]) {
                    res += neededTime[last];
                    last = i;
                    i++;
                } else {
                    res += neededTime[i];
                    i++;
                }
            } else {
                last = i;
                i++;
            }
        }
        return res;
    }
}

4. 代码优化说明

• 空间优化：无需额外数组或集合，仅用 last 和 res 两个临时变量，空间复杂度降至 O(1)。
• 时间优化：一次遍历完成所有逻辑，每个气球仅对比一次，时间复杂度为 O(n)，无冗余操作。
• 逻辑简化：去掉嵌套循环和冗余判断，通过「相邻对比」替代「整组遍历」，代码更简洁易读，执行效率更高。
• 边界兼容：自动处理「单个气球」「全相同颜色」「全不同颜色」等所有场景，无需额外判断。

5. 复杂度分析

• 时间复杂度：O(n)，其中 n 为气球数量。仅遍历数组一次，每个元素的对比和更新操作均为 O(1)。
• 空间复杂度：O(1)，仅使用常数级别的临时变量（res、last、i），无额外空间开销。

6. 总结

本题的核心是「贪心算法」的应用——通过「局部最优选择」实现「全局最优解」。每次仅在相邻两个相同颜色气球中，移除耗时更小的那个，最终所有连续相同组都会保留耗时最大的气球，总移除时间自然最小。

该解法的优势在于逻辑极简、效率拉满，避免了复杂的数据结构和嵌套逻辑，是本题的最优实现方式。解题关键在于看透「连续相同组的最大耗时可通过相邻对比迭代得到」的本质，无需过度复杂的设计，抓住核心矛盾即可快速求解。