车队 图解题解
一群车从不同位置冲向终点，追上了就合并成一队——从最近的车往后推，一次扫描数出几支车队。
高速公路上，从最靠近终点的车往后看：先把所有车按位置从右到左排，算出每辆车到达终点的时间。最右边的车永远是某队的领头。往左看下一辆：如果它到达时间 ≤ 当前领头车队的到达时间，说明它会在终点前追上那个车队，并入——继续以那个车队的到达时间为基准；如果它到达时间更长，说明它追不上，自己开一个新队，成为新的领头基准。每次只和「当前领头车队」比，而不是和上一辆单车比，这样合并才算对。
这道题到底在问什么
- 输入
- target=12, position=[10,8,0,5,3], speed=[2,4,1,1,3]
- 输出
- 3
最优解：一步一步想明白
- 3思路一句话：按起点从近到远排，算各车到终点的时间，用栈存车队到达时间；更慢就新车队入栈，更快会被合并。下面一步步演给你看。
- 4轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 5前面还没有车队，它就是第一个车队的领头车，记下它的到达时间。
- 6轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 7它到得比前面那个车队还晚，说明更慢、到终点前都追不上 → 它独立成一个新车队，到达时间压栈。
- 8轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 9它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 10轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 11它到得比前面那个车队还晚，说明更慢、到终点前都追不上 → 它独立成一个新车队，到达时间压栈。
- 12轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 13它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 14轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 15它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 16轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 17它到得比前面那个车队还晚，说明更慢、到终点前都追不上 → 它独立成一个新车队，到达时间压栈。
- 18轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 19它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 20轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 21它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 22轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 23它到得比前面那个车队还晚，说明更慢、到终点前都追不上 → 它独立成一个新车队，到达时间压栈。
- 24轮到这辆车（按起点从近到远）。先算它单独跑到终点要多久——时间越大跑得越慢。
- 25它到得比前面车队早（更快），会在终点前追上前车、被迫降速跟队 → 并入前车队，栈不变。
- 26所有车按起点从近到远扫完，栈里残留 5 个到达时间，就是 5 个车队。
⚠️ 容易写错的地方
✗ 错：按起点从远到近处理
✓ 对：按起点从近到远（position 降序）
只有离终点近的车才可能挡住后车，方向反了逻辑全错
✗ 错：比较位置或速度判合并
✓ 对：比较「到终点时间」
能不能追上由到达时间决定，位置/速度单看都不准
✗ 错：相等时间算两个车队
✓ 对：相等时算追上、合并（t ≤ 栈顶才并）
同时到达即同一车队，用严格 > 才入栈
完整代码（Python / C++ / Java）
Python
def carFleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True) # 按起点从近到远
stack = [] # 各车队领头车的到达时间
for p, s in cars:
t = (target - p) / s
if not stack or t > stack[-1]: # 比前车队慢 → 新车队
stack.append(t)
# 否则 t <= 栈顶：追上前车队，合并，不入栈
return len(stack)C++
int carFleet(int target, vector<int>& position, vector<int>& speed){
int n = position.size();
vector<int> idx(n);
for(int i=0;i<n;i++) idx[i]=i;
sort(idx.begin(), idx.end(), [&](int a,int b){ return position[a]>position[b]; });
vector<double> st; // 各车队到达时间
for(int i : idx){
double t = (double)(target - position[i]) / speed[i];
if(st.empty() || t > st.back()) st.push_back(t);
}
return st.size();
}Java
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> position[b] - position[a]); // 起点从近到远
Deque<Double> st = new ArrayDeque<>(); // 各车队到达时间(栈)
for (int i : idx) {
double t = (double) (target - position[i]) / speed[i];
if (st.isEmpty() || t > st.peek()) st.push(t); // 比前车队慢→新车队
}
return st.size();
}复杂度
时间
O(n log n)
排序主导；之后一次线性扫描，每辆车只判断一次
空间
O(n)
排序索引 + 到达时间栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 车队 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用到达时间而不是位置来判断合并？+
两车会不会在终点前相遇，取决于后车追前车的快慢，即各自单独到终点的时间：后车时间 ≤ 前车队时间就一定追上。位置只是起点，单看位置无法判断。
到达时间相等算一个车队还是两个？+
算一个。相等说明同时到达、后车始终贴着前车，属于同一车队，所以只有严格大于栈顶才压新栈。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 车队 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。