今天的Leetcode Daily：1578.繽紛氣球

主要還是分享一些有趣題目跟思路～覺得這題很巧妙就為他寫了一篇。
題目請往這裡走…

題目簡介

給定字串表示不同氣球的顏色，以及整數陣列表示移除氣球所需時間。連續同顏色的氣球需要被清除，求達到要求的最短時間。

思路

走過一次陣列之後，刪掉重複的部分會讓重複的部分剩下一顆氣球，如果移除不同需要不同時間，力求最短則勢必會留下移除時間最長者，對於每個需要移除的氣球最後花掉的時間為總時間減掉最長的時間。但似乎有辦法不需要紀錄同色氣球數量就知道要不要移除…？

題解

（可視化的看到過程）
對於每串同色氣球並不需要特別紀錄是否有重複

1. 沒有重複的話總值會等於最大值
2. 有重複的話結果增加(總值-最大值)

第一個狀況會使(總值-最大值)為0，不會影響結果。

Accepted 114 / 114 testcases passed
Runtime: 3ms (beats 72.07%)
Memory: 99.94MB (beats 35.01%)

class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int res = 0;
        int t = neededTime[0]; // total time
        int m = neededTime[0]; // max time
        for(int i = 1; i < colors.length(); i++){
            if(colors[i-1] == colors[i]){ // same color -> time++
                t += neededTime[i];
                m = max(m, neededTime[i]);
            }else{ // different color -> count time used, res++
                res += t-m;
                // balloon cnt = 1: total = max => res += 0
                // balloon cnt > 1: res = res + total - max
                t = neededTime[i];
                m = neededTime[i];
            }
        }
        return res+t-m; // remember to do the last operation
    }
};