a-z代表不同颜色的气球,相邻气球颜色相同的话每次可以保留其中一个,花费时间为二者needTime中间的较小值,问消除全部的相邻气球的最小总花费,贪心
#1578
#Runtime: 812 ms (Beats 62.22%)
#Memory: 22.1 MB (Beats 88.89%)
class Solution(object):
def minCost(self, colors, neededTime):
"""
:type colors: str
:type neededTime: List[int]
:rtype: int
"""
ans = 0
for i in xrange(1, len(neededTime)):
if colors[i] == colors[i - 1]:
ans += min(neededTime[i], neededTime[i - 1])
neededTime[i] = max(neededTime[i - 1], neededTime[i])
return ans