1578. Minimum Time to Make Rope Colorful

Leetcode link

题目简介

/**
 * @param {string} colors
 * @param {number[]} neededTime
 * @return {number}
 */

题目给我们一个字符串 colors 代表在一个绳子上按顺序不同气球的颜色；一个数字数组 neededTime 代表解开每一个气球所需要花的时间

题目要求我们解开任意数量的气球，使得两个相同颜色的气球不要相邻在一起，最后返回满足结果的所需最短时间是多少

解题思路

这一题我们分为三个步骤去求解：

1. 找到连续的同颜色的气球组合
2. 计算出将该组合的气球解到只剩一个所需的最短时间
3. 将所有组合的最短所需时间加总并返回

我们一步一步来解析：

1. 要找到连续同颜色的气球组合，我们需要用到两个指针形成一个窗口，该窗口理论上能把找到的组合包裹在内
2. 一旦有了窗口，我们就能得出需要的时间是解开该窗口所有气球的时间 - 该窗口需要解最久的气球的时间（换句话说，我们保留需要解最久的气球，把其他气球全解了）
3. 最后一步将其加总就好

让我们来看看代码：

Javascript

/**
 * @param {string} colors
 * @param {number[]} neededTime
 * @return {number}
 */
var minCost = function (colors, neededTime) {
    const len = colors.length
    let res = 0
    let left = 0

    while (left < len) {
        let right = left
        let curMax = neededTime[left]
        let curSum = neededTime[left]
        while (right < len - 1 && colors[right] === colors[right + 1]) {
            right++
            curMax = Math.max(curMax, neededTime[right])
            curSum += neededTime[right]
        }
        res += curSum - curMax
        left = right + 1
    }

    return res
};