拼车 图解题解
这道题到底在问什么
- 输入
- trips=[[2,1,5],[3,3,7]], capacity=4
- 输出
- false(站点 3 到 5 两段重叠,车上 5 人 > 4)
- 输入
- trips=[[2,1,5],[3,3,7]], capacity=5
- 输出
- true(峰值正好 5,等于容量)
最优解：一步一步想明白
- 3记住两步:① 每个行程在两端打 +/- 标记 ② 前缀和还原每站人数。下面每帧都在套这套。
- 4先开一个长度覆盖所有站点的数组 diff,全部填 0。下标就是站点号,值表示「在这一站人数的变化量」。
- 5行程 1([2,1,5]):2 人在站点 1 上车,就在 diff[1] 加上 2(紫色)。
- 6同一行程的 2 人在站点 5 下车,就在 diff[5] 减去 2(红色)。注意只动两端,中间各站不用碰。
- 7行程 2([3,3,7]):3 人在站点 3 上车,就在 diff[3] 加上 3(紫色)。
- 8同一行程的 3 人在站点 7 下车,就在 diff[7] 减去 3(红色)。注意只动两端,中间各站不用碰。
- 9两个行程都打完标记,diff 现在记录了「每站相对上一站的人数变化」。接下来从左往右累加(前缀和),就能还原每一站车上的真实人数。
- 10扫到站点 0:本站净变化 diff[0] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。
- 11结算后站点 0 车上 0 人,0 ≤ 4,这一站没问题,继续往后扫。
- 12扫到站点 1:本站净变化 diff[1] = 2。底色框出已累加过的前缀区间。准备把它加进 cur。
- 13结算后站点 1 车上 2 人,2 ≤ 4,这一站没问题,继续往后扫。
- 14扫到站点 2:本站净变化 diff[2] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。
- 15结算后站点 2 车上 2 人,2 ≤ 4,这一站没问题,继续往后扫。
- 16扫到站点 3:本站净变化 diff[3] = 3。底色框出已累加过的前缀区间。准备把它加进 cur。
- 17结算后站点 3 车上 5 人,5 > 4!此刻车坐不下,代码会在这一站直接返回 false。
- 18扫到站点 4:本站净变化 diff[4] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。
- 19站点 4 车上 5 人,仍 > 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。
- 20扫到站点 5:本站净变化 diff[5] = -2。底色框出已累加过的前缀区间。准备把它加进 cur。
- 21站点 5 车上 3 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。
- 22扫到站点 6:本站净变化 diff[6] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。
- 23站点 6 车上 3 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。
- 24扫到站点 7:本站净变化 diff[7] = -3。底色框出已累加过的前缀区间。准备把它加进 cur。
- 25站点 7 车上 0 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。
- 26扫到站点 8:本站净变化 diff[8] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。
- 27站点 8 车上 0 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。
- 28扫描全程,车上人数首次在站点 3 超过容量 4(红色),代码到这一站就返回了;全程峰值 5,所以无法完成所有行程,答案 false。
⚠️ 容易写错的地方
✗ 错：下车站也算占座
✓ 对：下车站要做 -人数,该站起人已下车
区间是左闭右开:[from, to) 才在车上,to 这一站人已离开
✗ 错：判超容量用 ≥
✓ 对：只有严格 > capacity 才失败
人数正好等于容量是允许的(样例 2 峰值 5 = 容量 5 仍为 true)
✗ 错：中间站逐格加人数
✓ 对：差分只动 from 和 to 两端
逐格加退化成 O(n·U),差分的全部意义就是只标两端
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0] * 1001
for num, start, end in trips:
diff[start] += num
diff[end] -= num
cur = 0
for x in diff:
cur += x
if cur > capacity:
return False
return TrueC++
#include <vector>
using namespace std;
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> diff(1001);
for (auto &t : trips) { diff[t[1]] += t[0]; diff[t[2]] -= t[0]; }
int cur = 0;
for (int x : diff) {
cur += x;
if (cur > capacity) return false;
}
return true;
}
};Java
import java.util.*;
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] diff = new int[1001];
for (int[] t : trips) { diff[t[1]] += t[0]; diff[t[2]] -= t[0]; }
int cur = 0;
for (int x : diff) {
cur += x;
if (cur > capacity) return false;
}
return true;
}
}复杂度
时间
O(n + U)
n 个行程各打一次标记,再扫一遍 U 个站点(U 为站点范围上界 1001)
空间
O(U)
一个长度 U 的差分数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 拼车 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不直接对每个行程的区间逐格加人数?+
那样每个行程要改 O(to-from) 格,最坏 O(n·U)。差分只在两端各改一格(O(1)/行程),最后一次 O(U) 前缀和统一还原,总 O(n+U),这正是差分相对暴力的提速点。
如果站点范围非常大(比如到 1e9),还能用定长差分数组吗?+
不能,会爆空间。这时把所有上车/下车事件按站点排序做「扫描线」:同一站点要先把该站的所有变化量累加成一个净值,再更新当前人数并检查峰值。这样才符合「到站下车的人这一站已不在车上」的左闭右开语义,避免同站先加后减造成的假超载。本质同差分,只是用排序的事件流代替定长数组,空间降到 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 拼车 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。