LeetCode 1094. 拼车——差分数组的时间线模拟
LeetCode 1094. 拼车——差分数组的时间线模拟
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等
开篇故事
从这篇开始，我们进入第三个小主题：差分数组与扫描线。
差分数组是一种极其简洁但经常被低估的技巧。它的本质是：把「对区间批量修改」的操作，转化为对区间端点的两次 O(1) 修改，然后用前缀和还原结果。
「拼车」这道题是差分数组的入门示范题。一辆车，不同乘客在不同站上下，问任意时刻车上人数是否超过容量。如果把每段上下客的操作用差分数组记录，然后还原前缀和，就能在 O(1) 记录每次事件，O(n) 统计任意时刻的人数。
一、题目解析
题目描述：
假设你是一位顺风车司机，车上最初有 capacity 个空座位。给定 trips 数组，trips[i] = [numPassengers, from, to] 表示第 i 次行程共有 numPassengers 名乘客，他们从 from 上车，到 to 下车（在 to 处下车前，他们在车上）。
如果能在所有给定的行程中接送所有乘客，则返回 true，否则 false。
示例：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true约束：
1 <= trips.length <= 10001 <= numPassengers <= 1000 <= from < to <= 1000
二、解法一：暴力模拟
思路分析
直接模拟每个站点的人数变化。创建一个数组 count[0..1000]，记录每个站点上下车的净变化，然后从左到右扫描，累计当前车上人数。
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] diff = new int[1001];
for (int[] trip : trips) {
int num = trip[0], from = trip[1], to = trip[2];
diff[from] += num; // from 站上车
diff[to] -= num; // to 站下车（在to之前还在车上）
}
int current = 0;
for (int i = 0; i <= 1000; i++) {
current += diff[i];
if (current > capacity) return false;
}
return true;
}
}这实际上就是差分数组的直接应用，O(n + max_stop) 时间，O(max_stop) 空间。
复杂度分析
- 时间复杂度：O(n + 1000)。n 是行程数，1000 是站点范围。
- 空间复杂度：O(1000)。
三、解法二：排序 + 模拟（优先队列）
思路分析
将所有事件按时间排序，用优先队列模拟：
import java.util.*;
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
// 将上车和下车事件展开为 [时间, 人数变化]
List<int[]> events = new ArrayList<>();
for (int[] trip : trips) {
events.add(new int[]{trip[1], trip[0]}); // 上车：+人数
events.add(new int[]{trip[2], -trip[0]}); // 下车：-人数
}
// 按时间排序，同一时间下车优先（先下后上）
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int current = 0;
for (int[] event : events) {
current += event[1];
if (current > capacity) return false;
}
return true;
}
}复杂度分析
- 时间复杂度：O(n log n)。排序。
- 空间复杂度：O(n)。
四、解法三（最优）：差分数组
核心思想
差分数组是专门为「区间更新 + 单点查询」设计的数据结构。
定义： 对于数组 a，其差分数组 diff 满足：diff[i] = a[i] - a[i-1]（diff[0] = a[0]）。
操作：
- 对区间
[l, r]所有元素加v：diff[l] += v; diff[r+1] -= v（O(1)） - 还原
a[i]的值：对diff求前缀和，a[i] = sum(diff[0..i])
本题中：乘客在 [from, to-1] 这段区间内在车上（到 to 站下车）：
diff[from] += numPassengersdiff[to] -= numPassengers（to 站下车，so to 站开始人数减少）
完整代码（差分数组标准模板）
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
// 找最大站点
int maxStop = 0;
for (int[] trip : trips) {
maxStop = Math.max(maxStop, trip[2]);
}
// 差分数组（大小 maxStop+1，索引 0~maxStop）
int[] diff = new int[maxStop + 1];
// 记录每次行程的上下车
for (int[] trip : trips) {
int num = trip[0], from = trip[1], to = trip[2];
diff[from] += num; // from 站开始上车
diff[to] -= num; // to 站开始下车
}
// 还原前缀和，检查任意时刻是否超容
int current = 0;
for (int i = 0; i <= maxStop; i++) {
current += diff[i];
if (current > capacity) return false;
}
return true;
}
}差分数组通用模板
// 初始化差分数组
int[] diff = new int[n + 1]; // 多一位防越界
// 区间 [l, r] 加 v（0-indexed，闭区间）
void rangeAdd(int[] diff, int l, int r, int v) {
diff[l] += v;
if (r + 1 < diff.length) diff[r + 1] -= v;
}
// 还原原数组（求前缀和）
int[] restore(int[] diff, int n) {
int[] arr = new int[n];
arr[0] = diff[0];
for (int i = 1; i < n; i++) {
arr[i] = arr[i - 1] + diff[i];
}
return arr;
}复杂度分析
- 时间复杂度：O(n + maxStop)。n 次操作 O(1)，还原 O(maxStop)。
- 空间复杂度：O(maxStop)。
五、举一反三
差分数组适用于「批量区间修改 + 最终还原」的场景：
| 题目 | 差分数组的应用 |
|---|---|
| 1094. 拼车 | 时间区间内乘客人数 |
| 253. 会议室II | 同一时刻最多几个会议（下一篇） |
| 1109. 航班预订统计 | 座位预订量 |
| 370. 区间加法 | 差分数组最基础的形式 |
六、踩坑实录
坑一：to 站点是「离车」的时刻
题目说「在 to 处下车」，意味着乘客在 to 站之前（[from, to-1] 这段）都在车上，to 站开始不在了。所以：
diff[from] += num（from 站开始有这些人）diff[to] -= num（to 站开始这些人不在了）
不要写成 diff[to-1+1] = diff[to]，其实就是 diff[to]，但理解清楚「to 站是下车时刻，to 站本身这些人不在车上」。
坑二：差分数组大小要多开一位
diff[to] -= num 可能访问 diff[maxStop]，如果数组大小只有 maxStop，就越界了。通常开 maxStop + 1 或 maxStop + 2 的大小。
坑三：同一时刻「先下后上」的顺序问题
本题差分数组方法不存在顺序问题（数组记录的是净变化，下车-num 和上车+num 是不同时刻）。但在排序 + 模拟的解法二中，同一站点如果有人上车也有人下车，应该先处理下车再处理上车，否则可能出现短暂超容的误判。
差分数组方法天然避免了这个问题。
七、总结
拼车是差分数组最直观的入门题。差分数组的精髓在于：把区间操作拆成两个端点操作，用 O(1) 记录，最后一次性还原所有结果。
这个思路在很多「事件调度」「区间统计」问题中都非常有用，是扫描线算法的前身。下一篇讲会议室 II，是差分数组和扫描线的综合应用。