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

【LetMeFly】2391.收集垃圾的最少总时间：不用那么多种方法，看透问题实质即可

力扣题目链接：https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/

给你一个下标从 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

解题方法：看透实质，一次遍历

题目中可以获得的信息：

1. 同一时刻只有一辆车能有操作
2. 一种车只能收集一种垃圾
3. 车辆容量无限
4. 车辆无需达到每一间房子，也无需返回
5. 一个时间只能收集一包垃圾

那么也就是说：

车G走一步、车M走一步、车P走一步、车G走一步、…

其实等价于

车G先走，走到最后一家有G垃圾的房间熄火。车M开始走，走到最后一家有M垃圾的房间熄火。最后车G走到最后一家有G垃圾的房间。

因此，我只需要遍历一遍垃圾数组，得知三辆车分别要走多远不就可以求出总的“移动耗时”了么？

又有$总耗时=移动耗时+收垃圾耗时$，而收垃圾耗时就是垃圾总数。

因此，遍历垃圾数组的时候，顺便统计一下垃圾一共多少袋不就可以求出总的“收垃圾耗时”了么？

• 时间复杂度$O(len(garbage))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {  // MPG
        int ans = 0;
        int last[3] = {0};
        char collect[3] = {'M', 'P', 'G'};
        for (int i = 0; i < garbage.size(); i++) {
            ans += garbage[i].size();
            for (char c : garbage[i]) {
                for (int j = 0; j < 3; j++) {
                    if (c == collect[j]) {
                        last[j] = i;
                    }
                }
            }
        }
        for (int i = 0; i < travel.size(); i++) {
            for (int j = 0; j < 3; j++) {
                if (last[j] >= i + 1) {
                    ans += travel[i];
                }
            }
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        ans = 0
        last = [0] * 3
        collect = 'MPG'
        for i in range(len(garbage)):
            ans += len(garbage[i])
            for c in garbage[i]:
                for j in range(3):
                    if c == collect[j]:
                        last[j] = i
        for i in range(len(travel)):
            for j in range(3):
                if last[j] >= i + 1:
                    ans += travel[i]
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/138702981