LeetCode 1109. 航班预订统计
题目描述
题意分析
一共有
n个航班，编号从一到n。每条预订记录[first, last, seats]表示闭区间first..last内的每一个航班，都额外预订了seats个座位。将所有记录叠加后，按航班顺序返回各自的总预订座位数。不同记录可以重叠，重叠航班需要累计全部贡献；不是把一笔座位数平分到区间中的航班。
解法：差分数组处理区间加法
核心思路
[!blue]
如果每条记录都逐个修改区间内航班，最坏会重复扫描整段数组。本题只在全部修改后读取最终结果，可以先记录变化发生的位置，再统一还原。
差分记录相邻航班总座位数的差。给闭区间统一加
seats时，区间内部每个位置都增加同样的量，相邻差值不变；只有起点相对前一个位置多了seats，终点后一位相对终点少了seats。所以每条记录只需“起点加，终点后减”两次修改。从一基航班编号转换为零基下标，起点是
first - 1，终点是last - 1，终点后一位恰好是last。因此更新answer[first - 1] += seats，若last < n，再更新answer[last] -= seats。若到最后一班才结束，数组内没有后续位置，无需取消。所有记录写完后从左到右做前缀和。扫描到某个航班时，已遇到的起点增量开始生效，已越过终点的增量被对应减量抵消，当前累计值正好等于覆盖这班的全部预订数。
加法可以叠加，不同记录的差分更新可以直接放在同一个数组里。这个数组先存变化量，前缀还原后再作为答案返回，不需要再开另一份空间。
解题步骤
- 创建长度为
n的全零数组，用作差分。- 对每条记录，在
first - 1加上预订座位数。- 若
last < n，在last减去相同座位数，取消区间结束后的影响。- 从下标一开始累加前一项，原地还原每班的真实总数。
- 返回还原后的数组。
代码实现
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] answer = new int[n];
for (int[] booking : bookings) {
answer[booking[0] - 1] += booking[2];
// 输入终点编号正好对应零基终点后一位，在此取消增量
if (booking[1] < n) {
answer[booking[1]] -= booking[2];
}
}
for (int i = 1; i < n; i++) {
// 前缀累加把差分变化量还原为真实座位数
answer[i] += answer[i - 1];
}
return answer;
}
}
func corpFlightBookings(bookings [][]int, n int) []int {
answer := make([]int, n)
for _, booking := range bookings {
answer[booking[0]-1] += booking[2]
// 输入终点编号正好对应零基终点后一位，在此取消增量
if booking[1] < n {
answer[booking[1]] -= booking[2]
}
}
for i := 1; i < n; i++ {
// 前缀累加把差分变化量还原为真实座位数
answer[i] += answer[i-1]
}
return answer
}
复杂度分析
- 时间复杂度：$O(q+n)$，其中 $q$ 为预订记录数。每条记录只更新两个端点，最后线性恢复全部航班。
- 空间复杂度：除返回数组外为 $O(1)$；长度为 $n$ 的答案数组同时承担差分存储。
关键点总结
[!green]
- 区间内统一增加只改变两处边界差值，逐条更新无需遍历整段。
- 闭区间终点仍应获得座位，取消位置在它后面。
- 差分先叠加、最后前缀恢复，适合只在全部修改后读取结果的场景。
- 一基编号下的
last，恰好对应零基数组的终点后一位。
易错点总结
[!yellow]
- 在
last - 1处扣除，会让闭区间最后一班提前失去本次贡献。last == n时不能访问answer[n]，取消点已在需要输出的范围之外。- 起点增量要使用
+=，不能覆盖之前预订记录。- 更新完差分就直接返回，得到的仍是变化量；必须做前缀累加才能还原座位数。
- 将
seats当成区间内所有航班共享的总额，会误解题意，每一班都应增加完整数额。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 370. 区间加法 | 中等 | 同样把区间增加转成起点加、终点后一位减，最后前缀还原各位置总值。 |
| 1094. 拼车 | 中等 | 本题航班两端都包含，拼车下车位置不再占用；差分更新的右端下标因此不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！