LeetCode 1109. 航班预订统计
目录
题目描述
题意分析
有
n个航班，编号从 1 到n。每条预订记录形如[first, last, seats]，含义是编号落在first到last之间（含两端）的每一个航班，各自增加seats个座位。所有记录处理完之后，要返回一个长度为n的数组，第i位是第i + 1号航班的总座位数。值得注意的是，题目只在全部操作结束后问一次结果，中途不需要查询任何航班的当前值。这是一个很强的信号：修改次数远多于查询次数，而且查询是一次性的批量查询，因此完全不必让每次修改都立刻把区间里每个位置改到位。
规模上航班数和记录数都到两万量级，两者相乘是四亿，逐个位置更新的写法有超时风险。数值方面单条预订最多两万座位、最多两万条记录，累加上限约四亿，仍在 32 位有符号范围内，不必换成 64 位整数。边界需要留意编号是 1 开始的、
first可以等于last（只影响一个航班），以及last可以取到n（终点已经贴着数组末尾）。
解法：差分数组处理区间加法
核心思路
每条预订都给一段连续航班统一加座位。逐个位置更新会达到 $O(mn)$，但题目只在全部修改结束后查询一次，适合用差分数组。
令
diff[i]表示第i个位置相对前一个位置的变化量。给闭区间[left, right]增加seats，只需：
diff[left] += seats，表示从这里开始生效；- 若
right + 1 < n，令diff[right + 1] -= seats，表示从这里取消影响。区间内部的相邻差值没有变化，所以一次区间修改只需常数操作。所有预订处理后，对差分数组求前缀和即可恢复每个航班的真实座位数。
代码直接把返回数组当差分数组使用，避免再开一个同样大小的临时数组。
解题步骤
- 创建长度为
n的答案数组，初始也充当差分数组。- 对每条
[first, last, seats]，把起点转成 0-based 的first - 1，在该处加seats。last本身正好是 0-based 的「终点后一位」；若它小于n，在该处减seats。- 从左到右累加数组，使每一项变成真实座位数并返回。
对
[[1,2,10],[2,3,20],[2,5,25]]，差分标记累加后为[10,45,-10,-20,0]，前缀和得到[10,55,45,25,25]。
代码实现
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(m + n)$，其中 $m$ 是预订数量；每条预订常数更新，最后线性恢复答案。
- 空间复杂度：$O(1)$（不计必须返回的答案数组）。
关键点总结
- 「多次区间修改，最后统一查询」是差分数组的典型信号。
- 差分记录的是变化量，前缀和是它的逆运算。
- 输入航班编号从 1 开始，而数组下标从 0 开始；
booking[1]恰好对应终点后一位。- 终点为
n时无需写取消标记，因为影响延伸到数组末尾。- 若修改与查询交替出现，静态差分不再适用，应使用树状数组或带懒标记的线段树。
易错点总结
- 在
booking[1] - 1处减座位：会让最后一个受影响航班少算；应在终点后一位减。- 忘记 1-based 到 0-based 的转换：所有结果整体错一位。
- 直接返回差分标记：必须先做前缀和。
- 终点为
n仍写answer[n]：会数组越界。- 逐个遍历预订区间：最坏复杂度退化为 $O(mn)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 370. 区间加法 | 中等 | 差分的最裸模板，没有编号偏移与语义包装 |
| 1094. 拼车 | 中等 | 差分之后还要在前缀和过程中随时校验容量上限 |
| 253. 会议室 II | 中等 | 端点值域稀疏，需改用事件排序而非定长差分数组 |
| 303. 区域和检索 - 数组不可变 | 简单 | 差分的对偶面：不修改而多次区间求和，用前缀和 |
| 307. 区域和检索 - 数组可修改 | 中等 | 修改与查询交替出现，差分失效，需要树状数组 |