题目描述
思路解析动画文字版
记牢这一句:捡的时间躲不掉、是死数;省的是行驶,每辆车只要开到自己那种垃圾最后出现的房子就能收手。下面先把垃圾总量数清楚,同时记下每种垃圾最后出现在哪栋房子。
五栋房子一字排开 · 格里是各自的垃圾：舞台上五个格子就是五栋房子,格里写着这栋的垃圾串。房子之间要开的车程是 3、5、2、4。右边这张小表,我们用来记三辆车各自最后要开到哪栋房子,现在还都是待定。接下来分两步:先一栋栋数垃圾总量、顺手记下每种垃圾最后露面的位置,再派三辆车去跑行驶。
房子 0 · 捡走 MPG 共 3 单位：来到房子 0,它的垃圾是 MPG,一共 3 个字符,捡它们要 3 分钟,累加到垃圾总量。同时把这栋出现的 M、P、G 记成最新的最后出现位置,右表里对应的车就更新成房子 0。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
房子 1 · 捡走 MP 共 2 单位：来到房子 1,它的垃圾是 MP,一共 2 个字符,捡它们要 2 分钟,累加到垃圾总量。同时把这栋出现的 M、P 记成最新的最后出现位置,右表里对应的车就更新成房子 1。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
房子 2 · 捡走 G 共 1 单位：来到房子 2,它的垃圾是 G,一共 1 个字符,捡它们要 1 分钟,累加到垃圾总量。同时把这栋出现的 G 记成最新的最后出现位置,右表里对应的车就更新成房子 2。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
房子 3 · 捡走 MP 共 2 单位：来到房子 3,它的垃圾是 MP,一共 2 个字符,捡它们要 2 分钟,累加到垃圾总量。同时把这栋出现的 M、P 记成最新的最后出现位置,右表里对应的车就更新成房子 3。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
房子 4 · 捡走 G 共 1 单位：来到房子 4,它的垃圾是 G,一共 1 个字符,捡它们要 1 分钟,累加到垃圾总量。同时把这栋出现的 G 记成最新的最后出现位置,右表里对应的车就更新成房子 4。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
垃圾数完 · 总量 9,三车终点已定：五栋房子全数完,垃圾总量是 9 分钟,这个数已经锁死,无论怎么派车都得花。再看右表:金属 M 最后出现在房子 3,纸 P 也在房子 3,玻璃 G 在房子 4。这三栋就是三辆车各自的终点。接下来只剩一件事:算三辆车分别开到终点要花多少行驶时间。
金属车 M 出发 · 目标终点房子 3：金属车 M 只收 M 这一种垃圾。它要开到 M 最后出现的房子 3 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
金属车 M · 房子 0 开到 房子 1,车程 3：金属车 M 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 3,继续往右开。
金属车 M · 房子 1 开到 房子 2,车程 5：金属车 M 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 3,继续往右开。
金属车 M · 房子 2 开到 房子 3,车程 2：金属车 M 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。到了房子 3,这就是 M 最后出现的地方,金属车 M 收工,它这一趟总行驶 10 分钟。
纸张车 P 出发 · 目标终点房子 3：纸张车 P 只收 P 这一种垃圾。它要开到 P 最后出现的房子 3 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
纸张车 P · 房子 0 开到 房子 1,车程 3：纸张车 P 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 3,继续往右开。
纸张车 P · 房子 1 开到 房子 2,车程 5：纸张车 P 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 3,继续往右开。
纸张车 P · 房子 2 开到 房子 3,车程 2：纸张车 P 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。到了房子 3,这就是 P 最后出现的地方,纸张车 P 收工,它这一趟总行驶 10 分钟。
玻璃车 G 出发 · 目标终点房子 4：玻璃车 G 只收 G 这一种垃圾。它要开到 G 最后出现的房子 4 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
玻璃车 G · 房子 0 开到 房子 1,车程 3：玻璃车 G 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 4,继续往右开。
玻璃车 G · 房子 1 开到 房子 2,车程 5：玻璃车 G 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 4,继续往右开。
玻璃车 G · 房子 2 开到 房子 3,车程 2：玻璃车 G 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。还没到终点房子 4,继续往右开。
玻璃车 G · 房子 3 开到 房子 4,车程 4：玻璃车 G 从房子 3 开到房子 4,这一段车程是 4 分钟,加进它的行驶,现在累计 14。到了房子 4,这就是 G 最后出现的地方,玻璃车 G 收工,它这一趟总行驶 14 分钟。
三车行驶合计 34 · 加垃圾总量 = 43：三辆车都跑完了。金属车和纸车都开到房子 3,各花 10 分钟行驶;玻璃车开到房子 4,花 14 分钟。三段行驶加起来是 34 分钟。再把一开始锁死的垃圾总量 9 分钟加上,总时间就是 43 分钟,和题目给的答案对上了。
边界想清:某种垃圾不存在就没有那辆车、只有一栋房子则零行驶、每种垃圾都取它最后出现处的前缀行驶。
面试重点:总时间拆成固定的捡拾加可省的行驶、每辆车只到该类垃圾最后出现处、前缀和一查即得、空间常数。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def garbageCollection(self, garbage: List[str], travel: List[int]) -> int: last = {} ans = 0 for i, s in enumerate(garbage): ans += len(s) for c in s: last[c] = i ts = 0 for i, t in enumerate(travel, 1): ts += t ans += sum(ts for j in last.values() if i == j) return ans复杂度
- 时间：O(L 加 n)，n 是房子数,L 是所有垃圾字符的总数。第一趟把每栋的字符扫一遍累加长度并更新 last,合起来是 L;第二趟沿 travel 走一遍是 n。每种垃圾只有 M、P、G 三类,last 表最多三行,是常数。整体随输入规模线性增长
- 空间：O(1)，按峰值算。除答案、前缀行驶等几个变量外,只有一张 last 表,而它最多只装 M、P、G 三个键,大小是常数,不随房子数增长。所以额外空间是常数级
易错点
面试追问把动画讲成自己的话
追问这题的核心贪心是什么?
追问为什么不用真的模拟三辆车怎么走?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
反转之后不同整数的数目
LeetCode 2442 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题