題目描述：

給你一個下標(biāo)從 0 開始的字符串?dāng)?shù)組 garbage ，其中 garbage[i] 表示第 i 個房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ，‘P’ 和 ‘G’ ，但可能包含多個相同字符，每個字符分別表示一單位的金屬、紙和玻璃。垃圾車收拾 一 單位的任何一種垃圾都需要花費(fèi) 1 分鐘。

同時給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 travel ，其中 travel[i] 是垃圾車從房子 i 行駛到房子 i + 1 需要的分鐘數(shù)。

城市里總共有三輛垃圾車，分別收拾三種垃圾。每輛垃圾車都從房子 0 出發(fā)，按順序 到達(dá)每一棟房子。但它們 不是必須 到達(dá)所有的房子。

任何時刻只有 一輛 垃圾車處在使用狀態(tài)。當(dāng)一輛垃圾車在行駛或者收拾垃圾的時候，另外兩輛車 不能 做任何事情。

請你返回收拾完所有垃圾需要花費(fèi)的 最少 總分鐘數(shù)。

示例 1：

輸入：garbage = [“G”,“P”,“GP”,“GG”], travel = [2,4,3]
輸出：21
解釋：
收拾紙的垃圾車：

1. 從房子 0 行駛到房子 1
2. 收拾房子 1 的紙垃圾
3. 從房子 1 行駛到房子 2
4. 收拾房子 2 的紙垃圾
   收拾紙的垃圾車總共花費(fèi) 8 分鐘收拾完所有的紙垃圾。
   收拾玻璃的垃圾車：
5. 收拾房子 0 的玻璃垃圾
6. 從房子 0 行駛到房子 1
7. 從房子 1 行駛到房子 2
8. 收拾房子 2 的玻璃垃圾
9. 從房子 2 行駛到房子 3
10. 收拾房子 3 的玻璃垃圾
    收拾玻璃的垃圾車總共花費(fèi) 13 分鐘收拾完所有的玻璃垃圾。
    由于沒有金屬垃圾，收拾金屬的垃圾車不需要花費(fèi)任何時間。
    所以總共花費(fèi) 8 + 13 = 21 分鐘收拾完所有垃圾。

示例 2：

輸入：garbage = [“MMM”,“PGM”,“GP”], travel = [3,10]
輸出：37
解釋：
收拾金屬的垃圾車花費(fèi) 7 分鐘收拾完所有的金屬垃圾。
收拾紙的垃圾車花費(fèi) 15 分鐘收拾完所有的紙垃圾。
收拾玻璃的垃圾車花費(fèi) 15 分鐘收拾完所有的玻璃垃圾。
總共花費(fèi) 7 + 15 + 15 = 37 分鐘收拾完所有的垃圾。

提示：

2 <= garbage.length <= 10⁵
garbage[i] 只包含字母 ‘M’ ，‘P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

解題思路一：處理垃圾和路程單獨(dú)計算。

1. 所有垃圾事一定要處理完的！for g in garbage: ans += len(g)
2. 反向遍歷garbage數(shù)組，得到每個垃圾車需要到達(dá)的最遠(yuǎn)距離，即可計算出所需路程時間。

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = 0for g in garbage:ans += len(g)G, M, P = 0, 0, 0for i in range(len(garbage) - 1, 0, -1):if 'G' in garbage[i]:G = ians += sum(travel[:G])breakfor i in range(len(garbage) - 1, 0, -1):if 'M' in garbage[i]:M = ians += sum(travel[:M])breakfor i in range(len(garbage) - 1, 0, -1):if 'P' in garbage[i]:P = ians += sum(travel[: P])breakreturn ans# 簡化
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = sum(map(len, garbage))for c in "GMP":for i, g in enumerate(reversed(garbage)):if c in g:ans += sum(travel[:n-i-1])breakreturn ans

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

解題思路二：逆向思維，計算多走的路

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = sum(map(len, garbage)) + sum(travel) * 3for c in "MPG":for g, t in zip(reversed(garbage), reversed(travel)):if c in g:breakans -= t  # 沒有垃圾 c，多跑了return ans

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

解題思路三：只記錄，當(dāng)前t需要計算幾次

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = len(garbage[0])seen = set()for g, t in zip(reversed(garbage), reversed(travel)):seen.update(g)ans += len(g) + t * len(seen)return ans

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

---

創(chuàng)作不易，觀眾老爺們請留步… 動起可愛的小手，點(diǎn)個贊再走唄 (???￩?) 歡迎大家關(guān)注筆者，你的關(guān)注是我持續(xù)更博的最大動力

原創(chuàng)文章，轉(zhuǎn)載告知，盜版必究

---

---

---

? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ? ⊕ ?