文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题使绳子变成彩色的最短时间出处1578. 使绳子变成彩色的最短时间难度5 级题目描述要求Alice 把n \texttt{n}n个气球排列在一根绳子上。给定一个下标从0 \texttt{0}0开始的字符串colors \texttt{colors}colors其中colors[i] \texttt{colors[i]}colors[i]是第i \texttt{i}i个气球的颜色。Alice 想要把绳子装扮成彩色。她不希望两个连续的气球涂着相同的颜色所以她请 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成彩色。给定一个下标从0 \texttt{0}0开始的整数数组neededTime \texttt{neededTime}neededTime其中neededTime[i] \texttt{neededTime[i]}neededTime[i]是 Bob 从绳子上移除第i \texttt{i}i个气球需要的时间以秒为单位。返回 Bob 使绳子变成彩色需要的最少时间。示例示例 1输入colors abaac, neededTime [1,2,3,4,5] \texttt{colors abaac, neededTime [1,2,3,4,5]}colors abaac, neededTime [1,2,3,4,5]输出3 \texttt{3}3解释在上图中‘a’ \texttt{a}‘a’是蓝色‘b’ \texttt{b}‘b’是红色‘c’ \texttt{c}‘c’是绿色。Bob 可以移除下标2 \texttt{2}2的蓝色气球。这将花费3 \texttt{3}3秒。移除后不存在两个连续的气球涂着相同的颜色。总时间是3 \texttt{3}3。示例 2输入colors abc, neededTime [1,2,3] \texttt{colors abc, neededTime [1,2,3]}colors abc, neededTime [1,2,3]输出0 \texttt{0}0解释绳子已经是彩色的。Bob 不需要从绳子上移除任何气球。示例 3输入colors aabaa, neededTime [1,2,3,4,1] \texttt{colors aabaa, neededTime [1,2,3,4,1]}colors aabaa, neededTime [1,2,3,4,1]输出2 \texttt{2}2解释Bob 会移除下标0 \texttt{0}0和下标4 \texttt{4}4处的气球。每个气球各需要1 \texttt{1}1秒来移除。移除后不存在两个连续的气球涂着相同的颜色。总时间是1 1 2 \texttt{1} \texttt{1} \texttt{2}112。数据范围n colors.length neededTime.length \texttt{n} \texttt{colors.length} \texttt{neededTime.length}ncolors.lengthneededTime.length1 ≤ n ≤ 10 5 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{5}1≤n≤1051 ≤ neededTime[i] ≤ 10 4 \texttt{1} \le \texttt{neededTime[i]} \le \texttt{10}^\texttt{4}1≤neededTime[i]≤104colors \texttt{colors}colors仅由小写英语字母组成解法思路和算法将字符串colors \textit{colors}colors分成连续非空子片段每个子片段由相同字符组成且任意两个相邻子片段的字符都不同。移除气球使绳子上的任意两个相邻气球不同色等价于从字符串colors \textit{colors}colors中移除字符使剩余的任意两个相邻字符不同。为了使字符串colors \textit{colors}colors中剩余的任意两个相邻字符不同每个片段最多只能保留1 11个字符因此对于长度为k kk的片段需要移除k − 1 k - 1k−1个字符当k 1 k 1k1时也成立。为了使总时间最少对于长度为k kk的片段应移除用时最少的k − 1 k - 1k−1个气球保留用时最多的1 11个气球理由如下。假设移除每个气球的时间分别是t 1 t_1t1到t k t_ktk其中t k t_ktk为最大值记T TT为移除当前片段中的用时最少的k − 1 k - 1k−1个气球且保留用时t k t_ktk的气球的总用时。如果保留的气球不是用时t k t_ktk的气球则将保留的气球的用时记为t j t_jtj将此时移除k − 1 k - 1k−1个气球的总用时记为T ′ TT′则t j ≤ t k t_j \le t_ktj≤tkT ′ T t k − t j ≥ T T T t_k - t_j \ge TT′Ttk−tj≥T总用时不可能小于T TT。因此总时间最少的方法是移除用时最少的k − 1 k - 1k−1个气球保留用时最多的1 11个气球。根据上述分析可以使用贪心的思想计算使绳子变成彩色需要的最少时间。具体做法是从左到右遍历字符串colors \textit{colors}colors和数组neededTime \textit{neededTime}neededTime遍历过程中维护所有气球的总用时totalTime \textit{totalTime}totalTime、当前片段的气球的用时之和segmentTime \textit{segmentTime}segmentTime与当前片段的最大用时maxTime \textit{maxTime}maxTime。当遍历到下标i ii时执行如下操作。移除第i ii个气球需要的时间是neededTime [ i ] \textit{neededTime}[i]neededTime[i]将segmentTime \textit{segmentTime}segmentTime增加neededTime [ i ] \textit{neededTime}[i]neededTime[i]并用neededTime [ i ] \textit{neededTime}[i]neededTime[i]更新maxTime \textit{maxTime}maxTime。如果i n − 1 i n - 1in−1或colors [ i ] ≠ colors [ i 1 ] \textit{colors}[i] \ne \textit{colors}[i 1]colors[i]colors[i1]则下标i ii是当前片段的结束下标当前片段保留用时最多的1 11个气球且移除其余所有气球的最少时间是segmentTime − maxTime \textit{segmentTime} - \textit{maxTime}segmentTime−maxTime将totalTime \textit{totalTime}totalTime增加segmentTime − maxTime \textit{segmentTime} - \textit{maxTime}segmentTime−maxTime然后将segmentTime \textit{segmentTime}segmentTime和maxTime \textit{maxTime}maxTime都更新为0 00。遍历结束之后totalTime \textit{totalTime}totalTime即为使绳子变成彩色需要的最少时间。代码classSolution{publicintminCost(Stringcolors,int[]neededTime){inttotalTime0;intsegmentTime0;intmaxTime0;intncolors.length();for(inti0;in;i){segmentTimeneededTime[i];maxTimeMath.max(maxTime,neededTime[i]);if(in-1||colors.charAt(i)!colors.charAt(i1)){totalTimesegmentTime-maxTime;segmentTime0;maxTime0;}}returntotalTime;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是字符串colors \textit{colors}colors和数组neededTime \textit{neededTime}neededTime的长度。需要遍历字符串和数组一次计算最短时间每个下标处的操作时间是O ( 1 ) O(1)O(1)。空间复杂度O ( 1 ) O(1)O(1)。
