1109. 航班预订统计

[wengzc]

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

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

 

示例：

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

 

提示：

• 1 <= bookings.length <= 20000

• 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000

• 1 <= bookings[i][2] <= 10000

题目链接：https://leetcode-cn.com/problems/corporate-flight-bookings

[wengzc]

思路分析：运用差分数组——和前缀和思想非常类似，差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
// 差分数组
var corpFlightBookings = function (bookings, n) {
    let diff
    // 生成差分数组
    function createDifference(nums) {
        let len = nums.length
        diff = new Array(len)
        diff[0] = nums[0]
        for (let i = 1; i < len; i++) {
            // diff[i] 就是 nums[i] 和 nums[i-1] 之差
            diff[i] = nums[i] - nums[i - 1]
        }
    }
    // 给闭区间 [i,j] 增加 val（可以是负数）
    function increment(i, j, val) {
        diff[i] += val
        if (j <= diff.length - 2) {
            diff[j + 1] -= val
        }
    }
    // 获取结果
    function result() {
        let len = diff.length
        let res = new Array(len)
        res[0] = diff[0]
        // 根据差分数组构造结果数组
        for (let i = 1; i < len; i++) {
            res[i] = res[i - 1] + diff[i]
        }
        return res
    }

    let nums = (new Array(n)).fill(0)
    let len = bookings.length
    createDifference(nums)
    for (let i = 0; i < len; i++) {
        increment(bookings[i][0] - 1, bookings[i][1] - 1, bookings[i][2])
    }
    return result()
};