求解思路
想象你在管理一排座位的灯光,每次预订就是要把某个区间的灯都调亮一些。
暴力做法是挨个座位去加,但这太慢了。
差分数组的巧妙之处在于:
我们只在区间的起点做个"开始加"的标记,在区间终点的下一个位置做个"停止加"的标记,最后从头到尾扫一遍,遇到"开始加"就累加这个值,遇到"停止加"就把它减掉,这样一路累加下来就得到了每个位置的最终值。
举个例子,要给 2-5 号航班各加 25 个座位,我们只需要在位置 2 标记 +25,在位置 6 标记 -25,然后从前往后累加:
位置 1 是 0,位置 2 是 0+25=25,位置 3 是 25+25=50… 位置 6 是某值-25,这样位置 2-5 都自动累加上了 25,而位置 6 之后又恢复正常。
这个技巧把每次区间更新从逐个修改变成了只改两个端点,效率从 O(n) 提升到 O(1)。
完整代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public class Solution {
public static int[] corpFlightBookings(int[][] bookings, int n) {
// 创建差分数组,大小为 n+2 是为了避免边界判断
// cnt[i] 表示位置 i 相对于位置 i-1 的变化量
int[] cnt = new int[n + 2];
// 遍历所有预订记录,构建差分数组
// 每个预订记录对应两个关键操作点
for (int[] book : bookings) {
// book[0] 是起始航班(1-indexed)
// book[1] 是结束航班(1-indexed)
// book[2] 是预订的座位数
// 在起始位置标记增加 book[2] 个座位
cnt[book[0]] += book[2];
// 在结束位置的下一个位置标记减少 book[2] 个座位
// 表示从 book[1]+1 位置开始,这 book[2] 个座位的影响结束
cnt[book[1] + 1] -= book[2];
}
// 通过前缀和还原实际值
// cnt[i] 累加 cnt[i-1] 后,表示第 i 个航班的实际预订座位数
for (int i = 1; i < cnt.length; i++) {
cnt[i] += cnt[i - 1];
}
// 构建最终答案数组
// 注意:航班编号从 1 开始,所以 cnt[1] 对应答案的 ans[0]
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = cnt[i + 1]; // cnt 数组索引要偏移 1
}
return ans;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~