What is the key pattern to solve the Minimum Amount of Time to Collect Garbage problem?

The key pattern is array traversal combined with string manipulation, where you minimize travel time by stopping at the last house that has each type of garbage.

How do I avoid unnecessary travel in this problem?

By identifying the last house that contains each type of garbage, you ensure the trucks only travel as far as necessary.

What should I do if there are no garbage items for one of the types?

If a truck has no garbage to collect, it doesn't contribute to the total time. Simply skip it in the calculations.

How does the travel array influence the solution?

The travel array determines the time it takes to move between houses, and it's used to calculate the total time each truck spends collecting garbage.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of houses, since we iterate through the arrays to find the last collection points and sum the times.

#2391

Medium

auto_awesome数组·string

LeetCode 题解工作台

收集垃圾的最少总时间

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

数组字符串前缀和

题目描述

给你一个下标从 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 <= 10⁵
garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

lightbulb

解题思路

方法一：哈希表 + 前缀和

根据题目描述，每一辆垃圾车从房子 $0$ 出发，收集其中一种垃圾，按顺序前进，直到到达该种垃圾最后出现的房子下标为止。

因此，我们可以用一个哈希表 $\textit{last}$ 记录每种垃圾最后出现的房子下标。我们假设第 $i$ 种垃圾最后一次出现在第 $j$ 个房子，那么第 $i$ 辆车所需要的行驶时间为 $\textit{travel}[0] + \textit{travel}[1] + \cdots + \textit{travel}[j-1]$ 。注意，如果 $j = 0$ ，则不需要行驶时间。我们通过前缀和累计所有车辆的行驶时间，加上每种垃圾的总收集时间，即可得到答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(k)$ ，其中 $n$ 和 $k$ 分别是垃圾的数量和种类。本题中 $k = 3$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently identify the last collection points for each truck?
question_mark
Does the candidate use the travel array effectively to minimize unnecessary trips?
question_mark
Is the candidate able to break down the problem into smaller subproblems (garbage collection and travel time calculation)?

warning

常见陷阱

外企场景

error
Not considering the optimization where each truck only travels to the last house that has its garbage.
error
Overcomplicating the calculation by including unnecessary travel or not summing the garbage collection times correctly.
error
Failing to handle cases where one or more types of garbage are not present, which would affect the total time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are more than three types of garbage? This requires extending the approach to handle multiple garbage types.
arrow_right_alt
How would the solution change if travel times were not provided in advance? This would require a dynamic approach for calculating travel times.
arrow_right_alt
What if the garbage is arranged in a circular route? This would change how we calculate the travel times between houses.

help

常见问题

外企场景

继续练习

#2381 字母移位 II #2559 统计范围内的元音字符串数 #2055 蜡烛之间的盘子