差分可以当作前缀和的逆运算，令 $bi=a_i-a_{i-1}$，即相邻两数的差。在每一个点上记录变化数值，因为有增加有减少，通过求和判断是否有超过指定容量的情况发生，超过则代表无法满足要求。

差分数组的应用场景是，需要对某个区间[i…j]频繁地加或减某一值，避免每次都遍历这个区间。

leetcode574. 航班预定统计

1. 题目

这里有n个航班，它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表，表中第i条预订记录 bookings[i] = [j, k, l] 意味着我们在从 j 到 k的每个航班上预订了 l个座位。
请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

示例：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

2. 解答

设answer[i]表示第i个航班预订的座位数。定义一个差分数组d[]，d[i]表示第i个航班与第i-1个航班预订座位的差值，即d[i] =
answer[i] - answer[i - 1]。

这样，我们每次遍历到bookings[i] = [i, j, k]，就只需要将d[i]增加k，d[j +
1]减少k即可，因为i到j之间，航班预订数量是没有变化的。

相当于answer[i] - answer[i-1] = d[i]
------- answer[i] = answer[i-1] + d[i]
------- answer[i-1] = answer[i] – d[i]

最后，计算answer[i] = answer[i - 1] + d[i]，返回answer即可。

/*
差分又称为微分运算。将一个区间的表示转换为一个个小块的表示。
1，使用一个数组记录这种 微分运算，一次遍历。
2，前缀和一次遍历。
最终即可得到一个完整的函数
*/
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
    int *res = (int *)malloc(sizeof(int) * n);
    memset(res, 0, sizeof(int) * n);

    for (int i = 0; i < bookingsSize; i++) {
        int first = bookings[i][0] - 1;
        int end = bookings[i][1];
        res[first] += bookings[i][2];
        if (end < n) {
            res[end] -= bookings[i][2];
        }
    }

    for (int i = 1; i < n; i++) {
        res[i] += res[i - 1];
    }
    *returnSize = n;
    return res;
}

leetcode1094. 拼车

1. 题目

设你是一位顺风车司机，车上最初有capacity个空座位可以用来载客。由于道路的限制，
车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。
这儿有一份乘客行程计划表trips[][]，其中trips[i]=[num_passengers,start_location, end_location]包含了第i组乘客的行程信息：

必须接送的乘客数量；
乘客的上车地点；
以及乘客的下车地点。
这些给出的地点位置是从你的初始出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务
（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

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

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

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

示例 4：
输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

2. 解答

#define NUMSIZE 10000

bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
    int loc[NUMSIZE] = { 0 };
    int passengers = 0;
    int startPos = 0;
    int endPos = 0;

    for (int i = 0; i < tripsSize; i++) {
        passengers = trips[i][0];
        startPos = trips[i][1];
        endPos = trips[i][2];
        loc[startPos] = loc[startPos] + passengers;
        loc[endPos] = loc[endPos] - passengers;
    }

    passengers = 0;
    for (int i = 0; i < NUMSIZE; i++) {
        passengers += loc[i];
        if (passengers > capacity) {
            return false;
        }
    }
    return true;
}