题目

题目来源：力扣（LeetCode）

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

思路分析

差分数组对应的概念是前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组。

差分数组的性质：

  1. 对于原始数组arr[a, b, c, d]，其差分数组为：diff[a, b-a, c-b, d-c]
  2. 差分数组的前缀和数组 == 原始数组，即：求差分数组的前缀和数组，即可还原回去。[a, a + b-a, a+b-a + c-b, …]
  3. 对原始数组的区间增加，可以转化为对其差分数组的两点增加（ O(n) -> O(1) ）： 假设对arr[i … j]区间每个元素全部增加delta，则等价于：diff[i] += delta，diff[j+1] -= delta

对于该题，我们换一种思路理解：

  1. 将问题转换为：某公交车共有 n 站，第 i 条记录 bookings[i] = [i, j, k] 表示在 i 站上车 k 人，乘坐到 j 站，在 j+1 站下车，需要按照车站顺序返回每一站车上的人数
  2. 根据 1 的思路，定义 counter[] 数组记录每站的人数变化，counter[i] 表示第 i+1 站。遍历 bookings[]：bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i-1] += k，在 j+1 站减少 k 人即 counters[j] -= k
  3. 遍历（整理）counter[] 数组，得到每站总人数： 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]
  1. /**
  2.  * @param {number[][]} bookings
  3.  * @param {number} n
  4.  * @return {number[]}
  5.  */
  6. var corpFlightBookings = function(bookings, n) {
  7.     const nums = new Array(n).fill(0);
  8.     for (const booking of bookings) {
  9.         nums[booking[0] - 1] += booking[2];
  10.         if (booking[1] < n) {
  11.             nums[booking[1]] -= booking[2];
  12.         }
  13.     }
  14.     for (let i = 1; i < n; i++) {
  15.         nums[i] += nums[i - 1];
  16.     }
  17.     return nums;
  18. };

参考阅读：
https://leetcode-cn.com/problems/corporate-flight-bookings/solution/gong-shui-san-xie-yi-ti-shuang-jie-chai-fm1ef/
https://leetcode-cn.com/problems/corporate-flight-bookings/solution/5118_hang-ban-yu-ding-tong-ji-by-user9081a/
https://leetcode-cn.com/problems/corporate-flight-bookings/solution/hang-ban-yu-ding-tong-ji-by-leetcode-sol-5pv8/