2391-收集垃圾的最少总时间

给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i
个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G'
，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。

同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1
需要的分钟数。

城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发， 按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。

任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。

请你返回收拾完所有垃圾需要花费的 最少 总分钟数。

示例 1：

**输入：** garbage = ["G","P","GP","GG"], travel = [2,4,3]
**输出：** 21
**解释：**
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。

示例 2：

**输入：** garbage = ["MMM","PGM","GP"], travel = [3,10]
**输出：** 37
**解释：**
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

提示：

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

本题 视频讲解 已出炉，欢迎素质三连，在评论区分享你对这场周赛的看法~

---

由于「任何时刻只有一辆垃圾车处在使用状态」，所以我们可以把每种垃圾分别处理，累加耗时。

注意到，答案其实可以分为两部分：

• 所有垃圾的数目，即 garbage 中所有字符串的长度之和。
• 根据每一种字符在 garbage 中最后一次出现的下标，即每辆垃圾车必须向右开到的房子的最小值，得到每辆车需要开的最短距离。

遍历 garbage 可以求出。

[sol1-Python3]

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        ans = 0
        right = {}
        for i, s in enumerate(garbage):
            ans += len(s)
            for c in s:
                right[c] = i
        return ans + sum(sum(travel[:r]) for r in right.values())

[sol1-Go]

func garbageCollection(garbage []string, travel []int) (ans int) {
	right := [3]int{}
	for i, s := range garbage {
		ans += len(s)
		for j, c := range "MPG" {
			if strings.ContainsRune(s, c) {
				right[j] = i
			}
		}
	}
	for _, r := range right {
		for _, t := range travel[:r] {
			ans += t
		}
	}
	return
}

思考题

如果垃圾种类有 10^5 种（用数字编号），上述代码要如何优化呢？见 视频讲解 。