1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int minCost(String colors, int[] neededTime) {
char[] colorArray = colors.toCharArray();
int max = neededTime[0], count = 1, timeSum = neededTime[0], ans = 0;
for (int i = 1; i < colorArray.length; i++) {
char currColor = colorArray[i], lastColor = colorArray[i - 1];
if (currColor == lastColor) {
max = Math.max(max, neededTime[i]);
timeSum += neededTime[i];
count += 1;
} else {
if (count > 1) {
ans += timeSum - max;
}
max = neededTime[i];
count = 1;
timeSum = neededTime[i];
}
}
if (count > 1) {
ans += timeSum - max;
}
return ans;
}
}
|
就是把连续颜色的气球消成1个. 把需要时间最多的那个保留下来. 我们用count存连续颜色出现的次数, timeSum存把所有连续颜色气球扎破的时间. max存连续颜色气球中需要时间最多的.
时间复杂度: O(n)
空间复杂度: O(1)
