航班预订统计 图解题解
这道题到底在问什么
- 输入
- n = 5，bookings = [[1,2,10],[2,3,20],[2,5,25]]
- 输出
- [10,55,45,25,25]
最优解：一步一步想明白
- 3两步走：先把每条预订记成「左端 +seats、右端下一格 −seats」两个标记；最后做一次前缀和，把标记摊开成答案。下面一步步演。
- 4先准备一个长度为 5 的差分数组 diff，每一格都是 0。它不直接存座位，而是存「在这里座位发生了多少变化」。
- 5第 1 条预订：第 1 班到第 2 班，每班加 10 个座位。高亮区间就是要被加座的航班。
- 6左端标记：在区间起点下标 0 处加上 10。这代表「从这一班开始，每班多 10 个座位」。
- 7右端收尾：在区间右端的下一格下标 2 处减去 10。这代表「从这一班起，前面多加的 10 个座位不再算」，正好把加座限制在区间内。
- 8第 2 条预订：第 2 班到第 3 班，每班加 20 个座位。高亮区间就是要被加座的航班。
- 9左端标记：在区间起点下标 1 处加上 20。这代表「从这一班开始，每班多 20 个座位」。
- 10右端收尾：在区间右端的下一格下标 3 处减去 20。这代表「从这一班起，前面多加的 20 个座位不再算」，正好把加座限制在区间内。
- 11第 3 条预订：第 2 班到第 5 班，每班加 25 个座位。高亮区间就是要被加座的航班。
- 12左端标记：在区间起点下标 1 处加上 25。这代表「从这一班开始，每班多 25 个座位」。
- 13这条预订的右端是最后一班，再往后没有航班了，所以不需要记 −25：加座自然延续到结尾。
- 14三条预订都记完了，差分数组 diff = [10, 45, -10, -20, 0]。注意全程只改了几个位置，没有逐格循环。下面做前缀和把它摊开。
- 15前缀和登场：准备一个累加器 run=0，指针从最左格出发，依次把每格的增减量加进 run，得到的就是真实座位数。
- 16指针走到下标 0。这一格记的增减量是 10，马上把它累加进 run。左边绿色是已经还原好的航班。
- 17累加完成：run 变成 10，这就是第 1 班的真实座位数，写回下标 0。绿色又多了一格。
- 18指针走到下标 1。这一格记的增减量是 45，马上把它累加进 run。左边绿色是已经还原好的航班。
- 19累加完成：run 变成 55，这就是第 2 班的真实座位数，写回下标 1。绿色又多了一格。
- 20指针走到下标 2。这一格记的增减量是 -10，马上把它累加进 run。左边绿色是已经还原好的航班。
- 21累加完成：run 变成 45，这就是第 3 班的真实座位数，写回下标 2。绿色又多了一格。
- 22指针走到下标 3。这一格记的增减量是 -20，马上把它累加进 run。左边绿色是已经还原好的航班。
- 23累加完成：run 变成 25，这就是第 4 班的真实座位数，写回下标 3。绿色又多了一格。
- 24指针走到下标 4。这一格记的增减量是 0，马上把它累加进 run。左边绿色是已经还原好的航班。
- 25累加完成：run 变成 25，这就是第 5 班的真实座位数，写回下标 4。绿色又多了一格。
- 26扫到末尾，差分数组被前缀和摊开成最终答案 [10, 55, 45, 25, 25]，就是每个航班被订的总座位数。
⚠️ 容易写错的地方
✗ 错：下标没对齐：航班从 1 编号，直接用 first 当下标
✓ 对：左端用 first-1（0 基下标）
题目航班编号从 1 开始，数组下标从 0 开始，差一位会整体错位
✗ 错：把减号打在下标 last-1，以为对应 last 班
✓ 对：在 last 班的下一格（下标恰为 last）处 -seats
减的位置要在区间「下一格」，last 班的下一格对应下标 last，不是 last-1
✗ 错：差分数组只开 n 长，last=n 时右端越界
✓ 对：开 n+1 长，多留一格接收右端 -seats
当 last=n，右端下一格下标正好是 n，需要这一格兜底（前缀和时它不计入答案）
完整代码（Python / C++ / Java）
Python
def corpFlightBookings(bookings, n):
diff = [0] * (n + 1) # 多留一格放右端 -seats
for first, last, seats in bookings:
diff[first - 1] += seats # 左端 +seats
diff[last] -= seats # 右端下一格 -seats
ans = [0] * n
run = 0
for i in range(n):
run += diff[i] # 前缀和还原
ans[i] = run
return ansC++
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n){
vector<int> diff(n + 1, 0);
for (auto& b : bookings) {
diff[b[0] - 1] += b[2];
diff[b[1]] -= b[2];
}
vector<int> ans(n);
int run = 0;
for (int i = 0; i < n; i++) { run += diff[i]; ans[i] = run; }
return ans;
}Java
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1];
for (int[] b : bookings) {
diff[b[0] - 1] += b[2];
diff[b[1]] -= b[2];
}
int[] ans = new int[n];
int run = 0;
for (int i = 0; i < n; i++) { run += diff[i]; ans[i] = run; }
return ans;
}
}复杂度
时间
O(n + m)
m 条预订各打两个标记，再 O(n) 前缀和扫一遍；与区间长度无关
空间
O(n)
只额外用一个长度 n+1 的差分数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 航班预订统计 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
差分数组为什么能把「整段加」变快？+
普通做法对区间每一格都加，区间长 L 就要 L 次操作。差分只在左端 +、右端下一格 −，两次操作就记下了「这段都加了 seats」，真正摊开靠最后一次前缀和，总代价与区间长无关。
前缀和那一步在做什么？+
把差分数组从左到右累加：run 不断加上每格的增减量。run 在区间内因左端的 + 而升高、走出区间因右端的 − 而落回，于是每个位置的 run 恰好是它被所有预订累计加的座位数。
差分和前缀和是什么关系？+
互为逆运算。前缀和把「增量数组」还原成「累计数组」，差分把「累计数组」拆回「增量数组」。本题先用差分高效记区间修改，再用前缀和读出结果。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 航班预订统计 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。