Medium

题目描述

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

提示：

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

解题思路

解题思路

这道题的核心在于理解每种垃圾车只需要访问到最后一个包含对应垃圾类型的房屋即可，不需要访问所有房屋。

分析过程：

  1. 收集垃圾时间计算：每辆垃圾车在每个房屋收集垃圾的时间等于该房屋对应垃圾类型的数量
  2. 行驶时间优化：关键观察是每种垃圾车只需要行驶到最后一个包含该类型垃圾的房屋，无需继续前行
  3. 最后位置确定：遍历所有房屋，记录每种垃圾类型最后出现的位置
  4. 前缀和优化：使用前缀和数组预计算从起点到任意位置的累积行驶时间

算法步骤：

  1. 统计每种垃圾的总数量（收集时间）
  2. 找到每种垃圾最后出现的房屋位置
  3. 计算行驶时间的前缀和
  4. 对于每种存在的垃圾类型，计算总时间 = 收集时间 + 行驶到最后位置的时间

时间复杂度为 O(n + m)，其中 n 是房屋数量，m 是所有垃圾的总数量。空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int n = garbage.size();
        
        // 统计每种垃圾的数量和最后出现位置
        int count[3] = {0}; // M, P, G
        int lastPos[3] = {-1};
        
        for (int i = 0; i < n; i++) {
            for (char c : garbage[i]) {
                if (c == 'M') {
                    count[0]++;
                    lastPos[0] = i;
                } else if (c == 'P') {
                    count[1]++;
                    lastPos[1] = i;
                } else { // c == 'G'
                    count[2]++;
                    lastPos[2] = i;
                }
            }
        }
        
        // 计算前缀和
        vector<int> prefixSum(n, 0);
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
        }
        
        int result = 0;
        for (int i = 0; i < 3; i++) {
            if (lastPos[i] != -1) {
                result += count[i] + prefixSum[lastPos[i]];
            }
        }
        
        return result;
    }
};

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        n = len(garbage)
        
        # 统计每种垃圾的数量和最后出现位置
        count = {'M': 0, 'P': 0, 'G': 0}
        last_pos = {'M': -1, 'P': -1, 'G': -1}
        
        for i in range(n):
            for c in garbage[i]:
                count[c] += 1
                last_pos[c] = i
        
        # 计算前缀和
        prefix_sum = [0] * n
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + travel[i - 1]
        
        result = 0
        for garbage_type in ['M', 'P', 'G']:
            if last_pos[garbage_type] != -1:
                result += count[garbage_type] + prefix_sum[last_pos[garbage_type]]
        
        return result

public class Solution {
    public int GarbageCollection(string[] garbage, int[] travel) {
        int n = garbage.Length;
        
        // 统计每种垃圾的数量和最后出现位置
        int[] count = new int[3]; // M, P, G
        int[] lastPos = {-1, -1, -1};
        
        for (int i = 0; i < n; i++) {
            foreach (char c in garbage[i]) {
                if (c == 'M') {
                    count[0]++;
                    lastPos[0] = i;
                } else if (c == 'P') {
                    count[1]++;
                    lastPos[1] = i;
                } else { // c == 'G'
                    count[2]++;
                    lastPos[2] = i;
                }
            }
        }
        
        // 计算前缀和
        int[] prefixSum = new int[n];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
        }
        
        int result = 0;
        for (int i = 0; i < 3; i++) {
            if (lastPos[i] != -1) {
                result += count[i] + prefixSum[lastPos[i]];
            }
        }
        
        return result;
    }
}

var garbageCollection = function(garbage, travel) {
    const n = garbage.length;
    
    // 统计每种垃圾的数量和最后出现位置
    const count = {'M': 0, 'P': 0, 'G': 0};
    const lastPos = {'M': -1, 'P': -1, 'G': -1};
    
    for (let i = 0; i < n; i++) {
        for (const c of garbage[i]) {
            count[c]++;
            lastPos[c] = i;
        }
    }
    
    // 计算前缀和
    const prefixSum = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
    }
    
    let result = 0;
    for (const garbageType of ['M', 'P', 'G']) {
        if (lastPos[garbageType] !== -1) {
            result += count[garbageType] + prefixSum[lastPos[garbageType]];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n为房屋数量，m为所有垃圾的总数量。需要遍历所有房屋和所有垃圾字符
空间复杂度O(n)主要用于存储前缀和数组，其他变量为常数空间