1094. 拼车（中）

• 题目
• 题解：差分数组

题目

• 车上最初有 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

题解：差分数组

• 分析：车站就是原始数组全部初始化为0，上车和下车就是数组的修改区间，上多少人，就是在这个区间加多少，最后返回结果数组，用最多人的时候和容量比较判断超载没有。

class Solution:
    class Difference:
    # 差分数组
        def __init__(self, nums: List[int]):
            assert len(nums) > 0
            self.diff = [0] * len(nums)
            # 根据初始数组构造差分数组
            self.diff[0] = nums[0]
            for i in range(1, len(nums)):
                self.diff[i] = nums[i] - nums[i - 1]
        # 给闭区间 [i, j] 增加 val（可以是负数）
        def increment(self, i: int, j: int, val: int) -> None:
            self.diff[i] += val
            if j + 1 < len(self.diff):
                self.diff[j + 1] -= val
        # 返回结果数组
        def result(self) -> List[int]:
            res = [0] * len(self.diff)
            # 根据差分数组构造结果数组
            res[0] = self.diff[0]
            for i in range(1, len(self.diff)):
                res[i] = res[i - 1] + self.diff[i]
            return res
            
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        nums=[0]*1001 # 最多有 1001 个车站
        df=Solution.Difference(nums)
        for item in trips:
            val,i,j=item[0],item[1],item[2]-1# 第 trip[2] 站乘客已经下车，即乘客在车上的区间是 [trip[1], trip[2] - 1]
            df.increment(i,j,val)
        result=df.result()
        if max(result[i] for i in range(len(result))) >capacity:
            return False
        return True