收集垃圾的最少总时间 图解题解
这道题到底在问什么
- 输入
- garbage=["MPG","MP","G","MP","G"], travel=[3,5,2,4]
- 输出
- 43
- 输入
- garbage=["G","P","GP","GG"], travel=[2,4,3]
- 输出
- 21
最优解：一步一步想明白
- 3记牢这一句:捡的时间躲不掉、是死数;省的是行驶,每辆车只要开到自己那种垃圾最后出现的房子就能收手。下面先把垃圾总量数清楚,同时记下每种垃圾最后出现在哪栋房子。
- 4先认识数据舞台上五个格子就是五栋房子,格里写着这栋的垃圾串。房子之间要开的车程是 3、5、2、4。右边这张小表,我们用来记三辆车各自最后要开到哪栋房子,现在还都是待定。接下来分两步:先一栋栋数垃圾总量、顺手记下每种垃圾最后露面的位置,再派三辆车去跑行驶。
- 5第一步:数垃圾 + 记最后出现来到房子 0,它的垃圾是 MPG,一共 3 个字符,捡它们要 3 分钟,累加到垃圾总量。同时把这栋出现的 M、P、G 记成最新的最后出现位置,右表里对应的车就更新成房子 0。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
- 6第一步:数垃圾 + 记最后出现来到房子 1,它的垃圾是 MP,一共 2 个字符,捡它们要 2 分钟,累加到垃圾总量。同时把这栋出现的 M、P 记成最新的最后出现位置,右表里对应的车就更新成房子 1。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
- 7第一步:数垃圾 + 记最后出现来到房子 2,它的垃圾是 G,一共 1 个字符,捡它们要 1 分钟,累加到垃圾总量。同时把这栋出现的 G 记成最新的最后出现位置,右表里对应的车就更新成房子 2。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
- 8第一步:数垃圾 + 记最后出现来到房子 3,它的垃圾是 MP,一共 2 个字符,捡它们要 2 分钟,累加到垃圾总量。同时把这栋出现的 M、P 记成最新的最后出现位置,右表里对应的车就更新成房子 3。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
- 9第一步:数垃圾 + 记最后出现来到房子 4,它的垃圾是 G,一共 1 个字符,捡它们要 1 分钟,累加到垃圾总量。同时把这栋出现的 G 记成最新的最后出现位置,右表里对应的车就更新成房子 4。之所以每次直接覆盖,是因为我们只关心每种垃圾最后一次在哪露面。
- 10第一步收尾五栋房子全数完,垃圾总量是 9 分钟,这个数已经锁死,无论怎么派车都得花。再看右表:金属 M 最后出现在房子 3,纸 P 也在房子 3,玻璃 G 在房子 4。这三栋就是三辆车各自的终点。接下来只剩一件事:算三辆车分别开到终点要花多少行驶时间。
- 11第二步:派 金属车 M金属车 M 只收 M 这一种垃圾。它要开到 M 最后出现的房子 3 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
- 12第二步:金属车 M 行驶中金属车 M 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 3,继续往右开。
- 13第二步:金属车 M 行驶中金属车 M 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 3,继续往右开。
- 14第二步:金属车 M 行驶中金属车 M 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。到了房子 3,这就是 M 最后出现的地方,金属车 M 收工,它这一趟总行驶 10 分钟。
- 15第二步:派 纸张车 P纸张车 P 只收 P 这一种垃圾。它要开到 P 最后出现的房子 3 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
- 16第二步:纸张车 P 行驶中纸张车 P 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 3,继续往右开。
- 17第二步:纸张车 P 行驶中纸张车 P 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 3,继续往右开。
- 18第二步:纸张车 P 行驶中纸张车 P 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。到了房子 3,这就是 P 最后出现的地方,纸张车 P 收工,它这一趟总行驶 10 分钟。
- 19第二步:派 玻璃车 G玻璃车 G 只收 G 这一种垃圾。它要开到 G 最后出现的房子 4 就能停,再往右的房子它一点不用管。现在它停在房子 0,行驶还是 0。下面它一段一段往右开,每过一段车程就累加进它自己的行驶。
- 20第二步:玻璃车 G 行驶中玻璃车 G 从房子 0 开到房子 1,这一段车程是 3 分钟,加进它的行驶,现在累计 3。还没到终点房子 4,继续往右开。
- 21第二步:玻璃车 G 行驶中玻璃车 G 从房子 1 开到房子 2,这一段车程是 5 分钟,加进它的行驶,现在累计 8。还没到终点房子 4,继续往右开。
- 22第二步:玻璃车 G 行驶中玻璃车 G 从房子 2 开到房子 3,这一段车程是 2 分钟,加进它的行驶,现在累计 10。还没到终点房子 4,继续往右开。
- 23第二步:玻璃车 G 行驶中玻璃车 G 从房子 3 开到房子 4,这一段车程是 4 分钟,加进它的行驶,现在累计 14。到了房子 4,这就是 G 最后出现的地方,玻璃车 G 收工,它这一趟总行驶 14 分钟。
- 24收束:总时间三辆车都跑完了。金属车和纸车都开到房子 3,各花 10 分钟行驶;玻璃车开到房子 4,花 14 分钟。三段行驶加起来是 34 分钟。再把一开始锁死的垃圾总量 9 分钟加上,总时间就是 43 分钟,和题目给的答案对上了。
⚠️ 容易写错的地方
✗ 错：以为要想办法给三辆车分配路线来省捡垃圾时间
✓ 对：捡垃圾总量是固定的,只在行驶上做文章
每一单位垃圾迟早都要被收,总捡拾时间恒等于字符总数,和派车顺序无关,能优化的只有行驶
✗ 错：让每辆车都开到最后一栋房子
✓ 对：每辆车只开到它那种垃圾最后出现的房子
某种垃圾最后一次出现之后的房子里没有它,那辆车再往前开纯属浪费,到最后出现处就该停
✗ 错：担心三辆车同时开要算并行时间
✓ 对：同一时刻只有一辆车动,三段行驶直接相加
题目规定任何时刻只有一辆车工作,所以总行驶就是三辆车各自行驶之和,不存在并行折扣
✗ 错：把行驶时间按段重复累计到每种垃圾
✓ 对：开到房子 k 的行驶是固定前缀和,每辆车按自己终点取一次
三辆车都从 0 顺序前进,到房子 k 的行驶就是 travel 前 k 段之和,按各自终点取值即可,不必重算
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int garbageCollection(vector<string>& garbage, vector<int>& travel) {
unordered_map<char, int> last;
int ans = 0;
for (int i = 0; i < garbage.size(); ++i) {
auto& s = garbage[i];
ans += s.size();
for (char& c : s) {
last[c] = i;
}
}
int ts = 0;
for (int i = 1; i <= travel.size(); ++i) {
ts += travel[i - 1];
for (auto& [_, j] : last) {
if (i == j) {
ans += ts;
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int garbageCollection(String[] garbage, int[] travel) {
Map<Character, Integer> last = new HashMap<>(3);
int ans = 0;
for (int i = 0; i < garbage.length; ++i) {
String s = garbage[i];
ans += s.length();
for (char c : s.toCharArray()) {
last.put(c, i);
}
}
int ts = 0;
for (int i = 1; i <= travel.length; ++i) {
ts += travel[i - 1];
for (int j : last.values()) {
if (i == j) {
ans += ts;
}
}
}
return ans;
}
}复杂度
时间
O(L 加 n)
n 是房子数,L 是所有垃圾字符的总数。第一趟把每栋的字符扫一遍累加长度并更新 last,合起来是 L;第二趟沿 travel 走一遍是 n。每种垃圾只有 M、P、G 三类,last 表最多三行,是常数。整体随输入规模线性增长
空间
O(1)
按峰值算。除答案、前缀行驶等几个变量外,只有一张 last 表,而它最多只装 M、P、G 三个键,大小是常数,不随房子数增长。所以额外空间是常数级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 收集垃圾的最少总时间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心贪心是什么?+
把总时间拆成两块:捡垃圾和行驶。捡垃圾是所有字符总数,固定不变。行驶上,每种垃圾派一辆车,只需从房子 0 开到这种垃圾最后一次出现的房子。因为所有车都顺序前进,到某栋房子的行驶就是前缀和。答案就是字符总数加上三种垃圾各自到最后出现房子的前缀行驶。
为什么不用真的模拟三辆车怎么走?+
因为三辆车互不影响,各自的行驶只由它那种垃圾的最后出现位置决定,而到某房子的行驶是固定前缀和,与其他车无关。题目又规定同一时刻只有一辆车动,总行驶就是三者相加。所以只要求出每种垃圾的最后出现位置,查一次前缀和即可,不必模拟。
复杂度是多少?+
一趟扫所有字符累加长度并更新最后出现位置,一趟沿 travel 求前缀行驶,时间随字符总数和房子数线性增长。空间上只需一张记录最后出现的表,而垃圾只有三种,表最多三行,是常数,所以额外空间是 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 收集垃圾的最少总时间 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。