LeetCode 题解工作台
使绳子变成彩色的最短时间
Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。 Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以用双指针指向当前连续相同颜色的气球的首尾，然后计算出当前连续相同颜色的气球的总时间 ，以及最大的时间 。如果当前连续相同颜色的气球个数大于 ，那么我们可以贪心地选择保留时间最大的气球，然后移除其它相同颜色的气球，耗时 $s - mx$，累加到答案中。接下来继续遍历，直到遍历完所有气球。 时间复杂度 ，空间复杂度 。其中 为气球的个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
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.length1 <= n <= 1051 <= neededTime[i] <= 104colors仅由小写英文字母组成
解题思路
方法一：双指针 + 贪心
我们可以用双指针指向当前连续相同颜色的气球的首尾，然后计算出当前连续相同颜色的气球的总时间 ，以及最大的时间 。如果当前连续相同颜色的气球个数大于 ，那么我们可以贪心地选择保留时间最大的气球，然后移除其它相同颜色的气球，耗时 ，累加到答案中。接下来继续遍历，直到遍历完所有气球。
时间复杂度 ，空间复杂度 。其中 为气球的个数。
class Solution:
def minCost(self, colors: str, neededTime: List[int]) -> int:
ans = i = 0
n = len(colors)
while i < n:
j = i
s = mx = 0
while j < n and colors[j] == colors[i]:
s += neededTime[j]
if mx < neededTime[j]:
mx = neededTime[j]
j += 1
if j - i > 1:
ans += s - mx
i = j
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should understand how dynamic programming can minimize the removal time by handling repeated characters efficiently.
- question_mark
They should demonstrate the ability to track state transitions and handle consecutive characters with minimal time.
- question_mark
A successful candidate should consider space optimization, ensuring the approach runs in O(1) space.
常见陷阱
外企场景- error
Forgetting to update the removal time correctly when processing consecutive balloons with the same color.
- error
Not efficiently handling the state transition between colors, leading to a suboptimal solution.
- error
Misunderstanding the dynamic programming approach, which may lead to excessive computation or unnecessary space usage.
进阶变体
外企场景- arrow_right_alt
The problem could involve different balloon removal constraints or require tracking the number of removals.
- arrow_right_alt
The same concept can be applied to more complex sequences of colors or higher constraints.
- arrow_right_alt
The dynamic programming solution might be adapted for cases where there are additional conditions for removing balloons, such as prioritizing certain colors.