leetcode 1578 重复字母

遍历发现重复字母的区域，然后将对应cost数组片段进行排序，将其中代价小的均加起来。

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        count=0
        j=0
        i=0
        while i<len(s)-1:
            j=i+1
            if s[i]==s[j]:
                while  j<=len(s)-1 and s[i]==s[j]:
                    j+=1
                costvalue=sorted(cost[i:j])
                for t in range(len(costvalue)-1):
                    count+=costvalue[t]
                i=j
            else:
                i+=1


        return count

通过两个while,但只在一个while循环中加入i+=1,然后保留大的cost值，因为如果有重复字符，最后只能剩下最大的那一个，题目求出的result每次循环通过重复片段的cost值加和与最大cost值作差取出。
时间复杂度O(n)

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:

        j=0
        i=0
        ch=''
        result=0

        while i<len(s):
            ch=s[i]
            maxvalue=float('-inf')
            sumvalue=0
            while i< len(s) and s[i]==ch:
                maxvalue=max(maxvalue,cost[i])
                sumvalue+=cost[i]
                i+=1
            result+=sumvalue-maxvalue

        return result

通过每次相同字符求最小的代价，然后将最大值传递下去，保证保留下来的是最大值。

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        result=0
        minvalue=float('inf')
        for i in range(len(s)-1):
            if s[i]==s[i+1]:
                minvalue=min(cost[i],cost[i+1])
                cost[i+1]=max(cost[i],cost[i+1])
                result+=minvalue

        return result