【LeetCode每日一题】1109. 航班预订统计&&1094. 拼车 (差分数组)

差分数组

差分���组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

一、基本概念：

差分数组的定义如下：

假设原始数组为arr，差分数组为diff，其中diff[i] = arr[i] - arr[i-1]（0

根据差分数组的定义，可以通过对差分数组进行累加操作来还原出原始数组：

arr[0] = diff[0]arr[1] = diff[0] + diff[1]arr[2] = diff[0] + diff[1] + diff[2]...arr[i] = diff[0] + diff[1] + ... + diff[i]

差分数组的主要优势在于，通过对差分数组进行区间修改操作，可以在O(1)的时间复杂度内完成。例如，如果要将原始数组的某个区间[l, r]中的每个元素都增加一个常数val，可以通过修改差分数组来实现：

diff[l] += valdiff[r+1] -= val

通过修改差分数组后，只需要对差分数组进行一次累加操作即可还原出修改后的原始数组。

二、真题练习

1109. 航班预订统计

https://leetcode.cn/problems/corporate-flight-bookings/

这里有 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]

题目转化：

原数组是全0 数组，在 [1,2] 区间同时加上10… 求操作后的数组。

思路：

• 构造差分数组
• 对差分数组进行操作
• 将差分数组还原成结果数组。

  注意点：

  • 区间是闭合的，[first,last] 都是有预定的。

  • 因为编号是从1 开始的，因此是

    diff[first-1]+=seat;diff[last-1+1]-=seat;

    last可能溢出，因此diff 数组应该长度为last+1，用diff还原的时候需要将最后一位剔除。

    /** * @param {number[][]} bookings * @param {number} n * @return {number[]} */var corpFlightBookings = function(bookings, n) {    let diff = new Array(n+1).fill(0);    for(let i=0;i        const [first,last,seat]=bookings[i];        diff[first-1]+=seat;        diff[last]-=seat;    }    let res =[diff[0]];    for(let i=1;i        res.push(res[i-1]+diff[i]);    }    return res;}    // 由于最大值是1000    let diff = new Array(1001).fill(0);    for(let i = 0; i  capacity){            return false;        }    }    return true;}