Loading... > https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/description/?envType=daily-question&envId=2024-05-02 思路很容易想，三辆车是串行的，所以把三辆车收垃圾和路上消耗的时间加起来即可。 收垃圾的时间只需要遍历 `garbage` 数组，把每个房子的垃圾数加起来即可。 路上的时间可以维护一个 `travel` 数组的前缀和 `cost`，并且遍历每个房子。如果房子里有垃圾车对应的垃圾，说明垃圾车来过了该房子，将该垃圾车对应的路上消耗时间更新成 `cost` 。遍历完所有房子就可以找到每辆车到达每类垃圾最后一次出现的位置所消耗的时间，将三个时间求和即可。 ```c++ class Solution { public: int garbageCollection(std::vector<std::string>& garbage, std::vector<int>& travel) { const int n = garbage.size(); int collectCost = 0, metal = 0, plastic = 0, glass = 0; for (int i = 0, roadCost = 0; i < n; i++) { for (const auto &letter : garbage[i]) { if (letter == 'P') plastic = roadCost; else if (letter == 'G') glass = roadCost; else metal = roadCost; ++collectCost; } if (i < n - 1) roadCost += travel[i]; } return collectCost + metal + plastic + glass; } }; ``` - 时间复杂度：$O(mn)$ ，其中 $m$ 是 `garbage[i]` 的长度， $n$ 是 `garbage` 的长度。 - 空间复杂度：$O(C)$ ，其中 $C$ 是垃圾的种类数。 最后修改：2024 年 05 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏