前缀和题目：航班预订统计

题目

标题和出处

标题：航班预订统计

出处：1109. 航班预订统计

难度

5 级

题目描述

要求

有 $\text{n}$ 个航班，从 $\text{1}$ 到 $\text{n}$ 编号。

给定一个航班预订表的数组 $\text{bookings}$，其中 ${\text{bookings[i] = [first}}_{\text{i}}{\text{, last}}_{\text{i}}{\text{, seats}}_{\text{i}}\text{]}$ 表示从 ${\text{first}}_{\text{i}}$ 到 ${\text{last}}_{\text{i}}$（包含 ${\text{first}}_{\text{i}}$ 和 ${\text{last}}_{\text{i}}$）的每个航班上预订了 ${\text{seats}}_{\text{i}}$ 个座位。

返回一个长度为 $\text{n}$ 的数组 $\text{answer}$，其中 $\text{answer[i]}$ 是第 $\text{i}$ 个航班预订的座位总数。

示例

示例 1：

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

示例 2：

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

数据范围

• $\text{1}\le \text{n}\le \text{2}\times {\text{10}}^{\text{4}}$
• $\text{1}\le \text{bookings.length}\le \text{2}\times {\text{10}}^{\text{4}}$
• $\text{bookings[i].length}=\text{3}$
• $\text{1}\le {\text{first}}_{\text{i}}\le {\text{last}}_{\text{i}}\le \text{n}$
• $\text{1}\le {\text{seats}}_{\text{i}}\le {\text{10}}^{\text{4}}$

解法

思路和算法

由于题目中给的航班编号范围是 $1$ 到 $n$，答案数组的下标范围是 $0$ 到 $n-1$，因此需要将数组 $\text{bookings}$ 中的每个预订的开始航班和结束航班分别减 $1$ 转换成答案数组的下标。

最直观的做法是对于每个预订更新航班区间中的所有航班的座位数，最坏情况下每个预订需要 $O(n)$ 的时间更新航班的座位数，该时间复杂度过高，需要优化。

为了降低更新航班座位数的时间复杂度，需要使用差分数组。定义差分数组 $\text{diffs}$，对于 $0\le i<n$ 有 $\text{diffs}[i]=\text{answer}[i]-\text{answer}[i-1]$，这里规定 $\text{answer}[-1]=0$，因此 $\text{diffs}[0]=\text{answer}[0]$。

对于预订 $[\text{first},\text{last},\text{seats}]$，其中 $\text{first}$ 和 $\text{last}$ 已经转换成答案数组的下标，需要将答案数组 $\text{answer}$ 的下标区间 $[\text{first},\text{last}]$ 中的每个元素值都增加 $\text{seats}$，等价于 $\text{answer}[\text{first}]-\text{answer}[\text{first}-1]$ 增加 $\text{seats}$ 且 $\text{answer}[\text{last}+1]-\text{answer}[\text{last}]$ 减少 $\text{seats}$，答案数组的其余相邻元素之间的差值都不变，因此可以将 $\text{diffs}[\text{first}]$ 的值增加 $\text{seats}$ 和将 $\text{diffs}[\text{last}+1]$ 的值减少 $\text{seats}$，即可表示区间中的元素值变化。特别地，当 $\text{last}=n-1$ 时，$\text{last}+1$ 超出数组下标范围，因此不更新 $\text{diffs}[\text{last}+1]$ 的值。使用差分数组，对于每个预订只需要 $O(1)$ 的时间更新差分数组。

遍历所有预订之后，计算差分数组的前缀和数组，即为答案 $\text{answer}$。

实现方面，由于 $\text{diffs}[0]=\text{answer}[0]$ 且 $\text{answer}$ 是 $\text{diffs}$ 的前缀和数组，因此可以将 $\text{answer}$ 作为差分数组，最后对 $\text{answer}$ 计算前缀和并更新数组中的每个元素值，遍历结束之后的 $\text{answer}$ 即为答案。使用该实现方法，除了返回值以外不需要额外创建数组。

代码

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] answer = new int[n];for (int[] booking : bookings) {int first = booking[0] - 1, last = booking[1] - 1, seats = booking[2];answer[first] += seats;if (last < n - 1) {answer[last + 1] -= seats;}}for (int i = 1; i < n; i++) {answer[i] += answer[i - 1];}return answer;}
}

复杂度分析

• 时间复杂度：$O(n+b)$，其中 $n$ 是航班数量，$b$ 是数组 $\text{bookings}$ 的长度。需要遍历数组 $\text{bookings}$ 更新差分数组，每次更新的时间是 $O(1)$，计算答案数组需要遍历差分数组一次计算前缀和，时间是 $O(n)$，因此时间复杂度是 $O(n+b)$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。