拼车

标签: 数组 前缀和 排序 模拟 堆（优先队列）

难度: Medium

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

提示：

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengersi <= 100
  • 0 <= fromi < toi <= 1000
  • 1 <= capacity <= 105

Submission

运行时间: 17 ms

内存: 16.4 MB

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        dp = [0] * (max(trips, key=lambda x: x[2])[2] + 1)
        for t in trips:
            dp[t[1]] += t[0]
            dp[t[2]] -= t[0]
        return max([el for el in accumulate(dp)]) <= capacity

Explain

此题解采用的是差分数组的方法。首先，创建一个差分数组 dp，其长度为所有行程结束位置的最大值加一。对于每个行程 [numPassengers, from, to]，在差分数组的 from 位置增加 numPassengers，表示这点有乘客上车；在 to 位置减去 numPassengers，表示这点有乘客下车。之后，计算差分数组的前缀和，得到每个位置的车上乘客数。如果任何位置的乘客数超过了车辆的容量，返回 false；否则，如果所有位置的乘客数都不超过容量，返回 true。

时间复杂度: O(n + m)

空间复杂度: O(m)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 创建大小为行程最大结束位置加一的差分数组
        dp = [0] * (max(trips, key=lambda x: x[2])[2] + 1)
        for t in trips:
            # 在乘客上车点增加乘客数
            dp[t[1]] += t[0]
            # 在乘客下车点减少乘客数
            dp[t[2]] -= t[0]
        # 使用累积求和检查任何时刻的乘客数是否超过容量
        return max([el for el in accumulate(dp)]) <= capacity

Explore

在差分数组中，增加`from`位置的乘客数表示乘客从该位置开始上车，而在`to`位置减少乘客数表示乘客在该位置下车并不再占用车辆空间。通过这种处理，差分数组可以简洁地表示在任何给定位置的乘客数变化。计算这个数组的前缀和可以直接得到任何位置的实时乘客总数，从而有效地模拟整个行程中车辆的乘客变化情况。

差分数组的设计确保即使一个位置同时是多个行程的上车点和下车点，乘客的变化也能被准确记录。对于每个行程，在`from`位置增加乘客，在`to`位置减少乘客，无论这些操作发生多少次，都会被正确地累加或减去。因此，差分数组能够准确反映出每个地点的净乘客变化。

在这个特定的场景中，前缀和小于零的情况理论上不应该发生，因为它会意味着车上的乘客数为负，这在现实中是不可能的。前缀和代表车上的乘客数量，它从零开始累加，只有在有乘客上车时才会增加。如果前缀和在任何时刻为负，这可能表明代码实现或输入数据有误。然而，前缀和为零并不意味着车上始终有乘客，它可能表示车是空的。

使用`max`函数配合`accumulate`（累加生成器）是一种效率较高的方式来找出任何时刻乘客数的最大值。这样可以在一次遍历中确定是否有任何时刻的乘客数超过了车辆的容量。如果逐一检查每个位置的乘客数，虽然也可行，但使用`max`可以更快地得出结果，尤其是在数据量大时更为高效。