LeetCode 1109「航班预订统计」场景真实得不像算法题你收到2万条预订记录每条都是“从第a天到第b天每天加c个座位”。要你算出每一天的总座位数。大多数人第一反应forfirst, last, seatsinbookings:fordayinrange(first, last1):ans[day] seats「然后 TLE超时了。」2万条记录 × 平均1万天 2亿次加法不超时才怪。「但差分数组告诉你每条区间更新只需要改两个数。」 题目速览30 秒读懂有n个航班编号 1~n给你m条预订记录[first, last, seats]表示从first到last的每个航班都增加seats个座位。返回每个航班最终的座位总数。「示例」输入bookings [[1,2,10],[2,3,20],[2,5,25]], n 5 输出[10, 55, 45, 25, 25]「约束」n和m都 ≤ 2×10⁴暴力O(n*m)必挂。 核心思路区间更新 开头 关水龙头最后前缀和还原暴力到底慢在哪里每条记录要遍历它覆盖的所有航班区间越长越慢。而且多条记录之间相互独立无法复用中间结果。优化的数学本质——差分数组区间[first, last]统一加seats等价于在first处“开始加” →diff[first] seats在last1处“停止加” →diff[last1] - seats这就像一排水龙头你在位置1打开阀门流量 10在位置3关掉阀门流量 -10那么位置1~2都流了10位置3及以后不流「最后对整个diff做一次前缀和」就能还原出每个位置的最终值。「每条记录O(1)总共O(m)还原O(n)总复杂度O(mn)。」️ 图解全过程一眼就懂以bookings [[1,2,10],[2,3,20],[2,5,25]], n 5为例「Step 1差分数组初始全0」索引0123456diff0000000「Step 2处理每条记录只改两个位置」预订操作diff 变化[1,2,10]diff[1]10, diff[3]-10[0,10,0,-10,0,0,0][2,3,20]diff[2]20, diff[4]-20[0,10,20,-10,-20,0,0][2,5,25]diff[2]25, diff[6]-25[0,10,45,-10,-20,0,-25]「Step 3前缀和还原从左到右累加」航班 i累加过程结果1total 0 10「10」2total 10 45「55」3total 55 (-10)「45」4total 45 (-20)「25」5total 25 0「25」最终[10, 55, 45, 25, 25]✅看到了吗「无论区间多长每条记录只动了两个数。」 代码实现Python Java附防坑版Python 版classSolution:defcorpFlightBookings(self, bookings: List[List[int]], n: int)- List[int]:# 多开 2 个位置防止 last1 越界diff [0] * (n 2)forfirst, last, seatsinbookings:diff[first] seatsdiff[last 1] - seats# 前缀和还原ans [0] * ntotal 0foriinrange(1, n 1):total diff[i]ans[i -1] totalreturnansJava 版classSolution{publicint[] corpFlightBookings(int[][] bookings,intn) {int[] diff newint[n 2];// 多开 2 位防越界for(int[] b : bookings) {diff[b[0]] b[2];diff[b[1] 1] - b[2];}int[] ans newint[n];inttotal 0;for(inti 1; i n; i) {total diff[i];ans[i -1] total;}returnans;}}⚠️「致命坑必看」diff长度必须是n 2因为当last n时diff[n1]会被访问。少开一位会数组越界。还原时循环从1到n对应航班编号而ans下标是0到n-1。⏱️ 复杂度分析面试必问「处理预订」O(m)每条O(1)「前缀和还原」O(n)「总时间」O(m n)暴力是O(m × n)「空间」O(n)差分数组当m n 2×10⁴时差分数组4×10⁴次操作 vs 暴力4×10⁸次「差距1万倍」。 举一反三4 道高频变种题一套框架通吃题目差异点应对策略「LeetCode 1094. 拼车」区间上下车判断是否超载差分记录每站人数变化还原后检查是否超过容量「LeetCode 370. 区间加法」会员题纯差分模板直接套模板改两个位置 前缀和「LeetCode 1854. 人口最多的年份」出生-死亡区间找人口峰值年差分记录每年人口变化还原后找最大值「LeetCode 798. 得分最高的最小轮调」进阶区间加分求最大得分索引差分记录每个轮调位置的变化量 面试追问模拟提前准备惊艳全场「Q1差分数组和前缀和到底是什么关系」它们互为逆运算。原数组 → 差分数组相邻差diff[i] nums[i] - nums[i-1]差分数组 → 原数组前缀和nums[i] nums[i-1] diff[i]前缀和擅长“频繁区间查询”差分数组擅长“频繁区间更新”它们是同一枚硬币的两面。「Q2如果既有区间更新又有区间查询差分数组还够用吗」不够。差分数组只支持“最后统一查询”如果更新和查询交替频繁需要「树状数组Fenwick Tree「或」线段树」它们支持 O(log n) 的区间更新 区间查询。「Q3差分数组能处理二维区间更新吗比如子矩阵全部 v」可以。二维差分用容斥原理diff[x1][y1] vdiff[x21][y1] - vdiff[x1][y21] - vdiff[x21][y21] v最后对每一行做前缀和再对每一列做前缀和还原。 实战小技巧刷题党必备「口诀」区间更新左加右减前缀还原一路累加。「模板」凡是“给区间加同一个值最后求每个位置的值”直接用差分数组。「空间优化」如果不需要保留原始差分数组可以直接在答案数组上做差分原地操作节省O(n)空间。 实际应用场景不止是刷题「酒店/航班预订系统」批量统计各日期的房间/座位预订量「会议室调度」统计各时间段会议室占用数「交通流量分析」统计各路段在某时段内的车流量「游戏经验值分配」给某等级区间的玩家批量发放经验「工资/税务计算」某收入区间的税率批量调整 今日思考题如果bookings中既有“加座位”也有“退座位”负值差分数组需要改什么「提示」完全不用改seats可以为负数diff[first] seats和diff[last1] - seats逻辑完全通用。那如果每条记录不是“区间统一加”而是“区间统一赋值为某个值”差分数组还能用吗欢迎评论区讨论