[LeetCode] 1578. Minimum Time to Make Rope Colorful

Alice has n balloons arranged on a rope. You are given a 0-indexed string colors where colors[i] is the color of the ith balloon.

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the ith balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

Example 1:
Input: colors = “abaac”, neededTime = [1,2,3,4,5]
Output: 3
Explanation: In the above image, ‘a’ is blue, ‘b’ is red, and ‘c’ is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.

Example 2:
Input: colors = “abc”, neededTime = [1,2,3]
Output: 0
Explanation: The rope is already colorful. Bob does not need to remove any balloons from the rope.

Example 3:
Input: colors = “aabaa”, neededTime = [1,2,3,4,1]
Output: 2
Explanation: Bob will remove the ballons at indices 0 and 4. Each ballon takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.

Constraints:
n == colors.length == neededTime.length
1 <= n <= 105
1 <= neededTime[i] <= 104
colors contains only lowercase English letters.

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

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

思路

思路是贪心。对于任何两个连续的气球，如果他们的颜色相同，则需要去除 neededTime 更多的那个。
具体的实现上，对于任何两个连续的气球 i 和 i + 1，如果 i 的 neededTime 更多，则我们在累加 i + 1 的 neededTime 的同时，将 i 和 i + 1 的位置 swap 一下，这样就能使 i 可以跟后面的 i + 2 继续比较了。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            if (colors.charAt(i) == colors.charAt(i + 1)) {
                res += Math.min(neededTime[i], neededTime[i + 1]);
                if (neededTime[i] > neededTime[i + 1]) {
                    swap(neededTime, i, i + 1);
                }
            }
        }
        return res;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}