JZX轻语：简

LeetCode 2391 - 收集垃圾的最少总时间

发表于2024年05月11日

#前缀和 #模拟

还是模拟的题目，最理想的结果是每辆垃圾车都刚好停在对应垃圾所在的最后位置，不再往前开（没意义），因此最短时间为所有垃圾的处理时间（所有垃圾的数量）+ 三种类型的垃圾车到达该类型垃圾最终位置的用时。其中，前者可累加所有字符串的长度即可；后者则可使用前缀和的方法减少计算量（三次计算->一次计算）。

import itertools


class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        prev_sum = [0, *itertools.accumulate(travel)]
        last_garbage_type_poses = [-1, -1, -1]  # M, P, G最后一次出现的位置
        for i, garbage_type in enumerate(('M', 'P', 'G')):
            for pos in range(len(garbage) - 1, -1, -1):  # 倒过来找
                if garbage_type in garbage[pos]:
                    last_garbage_type_poses[i] = pos
                    break
        all_garbage_cnt = sum(len(g) for g in garbage)
        # 最终的用时 = (所有垃圾的数量) + (三种类型的垃圾车到达该类型垃圾最终位置的用时)
        ans = all_garbage_cnt
        for pos in last_garbage_type_poses:
            if pos != -1:
                ans += prev_sum[pos]
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/watering-plants-ii/