发表于 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 题目链接