车队问题为什么要按位置排序？Car Fleet 如何用排序加扫描解决？

简化版

车队问题先按车辆当前位置从靠近终点到远离终点排序，再计算每辆车到终点的时间 time = (target - position) / speed。从前往后扫：如果后车到达时间小于等于前方车队时间，说明它会追上并并入前方车队；如果后车时间更大，说明追不上前方车队，会形成新车队。统计新车队次数即可。

详细版

排序是这题的核心，因为车只能追上前面的车，不能越过终点前已经在后面的车。按位置降序后，扫描顺序就是“从最靠近终点的车队往后看”。维护当前前方车队的到达时间 lastTime：后车时间 t <= lastTime，会追上前方车队，车队数不变；若 t > lastTime，它更慢，追不上，自己成为新车队，并更新 lastTime = t。

int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    int[][] cars = new int[n][2];
    for (int i = 0; i < n; i++) cars[i] = new int[]{position[i], speed[i]};
    Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));

    int fleets = 0;
    double lastTime = -1.0;
    for (int[] car : cars) {
        double t = (double) (target - car[0]) / car[1];
        if (t > lastTime) {
            fleets++;
            lastTime = t;
        }
    }
    return fleets;
}

复杂度是排序 O(n log n)，扫描 O(n)，空间取决于是否额外建车数组。面试最常见坑是按位置升序扫，或者用距离/速度的整数除法导致精度错误。

完整版教学

一、题意里的“不能超车”决定了解法方向

Car Fleet 的关键规则是：后车追上前车后会变成同一个车队，并以较慢的速度一起走；车到终点前不能超过前面的车。这个规则意味着最终车队关系只会发生在“位置更靠后的车追位置更靠前的车”之间，因此必须先建立车辆在道路上的前后顺序。

如果不排序，输入数组顺序没有物理意义。比如 target=12，车辆位置 [10,8,0,5,3]，速度 [2,4,1,1,3]，数组里相邻不代表路上相邻。排序后得到位置从近到远：10、8、5、3、0，这时每辆车只需要和前方已经形成的车队比较到达时间。

位置	速度	到终点时间
10	2	1
8	4	1
5	1	7
3	3	3
0	1	12

二、为什么按位置降序扫描

按位置降序就是从最靠近终点的车开始看。它前面没有别的车，所以必然先形成一个候选车队。后面的车如果到达时间更短或相等，说明它原本会更早到终点，但因为在后面且不能超车，途中会追上前方车队，最后并入它；如果到达时间更长，说明它更慢，追不上，只能另成一队。

以 target=12 的例子看：位置 10 的车时间 1，位置 8 的车时间也是 1，它们到终点时相遇，算同一队。位置 5 的车时间 7，追不上时间为 1 的队，形成新队。位置 3 的车时间 3，能追上前面时间为 7 的慢队，合并。位置 0 的车时间 12，追不上前面慢队，形成新队，答案 3。

按位置降序：
10(t=1) -> 新队 last=1
8 (t=1) -> t<=1，合并
5 (t=7) -> t>1，新队 last=7
3 (t=3) -> t<=7，合并
0 (t=12)-> t>7，新队 last=12

记忆钩子：从终点往回看，后车只问一个问题：我到终点的时间是否比前方车队更晚？更晚就追不上，形成新队。

三、到达时间为什么能替代模拟追车

很多人会想计算两车相遇时间，但其实不需要。若后车单独到终点时间 tBack 小于等于前方车队到终点时间 tFront，说明在终点之前或终点处后车一定能追上前方车队。因为后车起点更靠后，却不晚于前车队到终点，它必须在某个位置追到。

若 tBack > tFront，后车单独到终点都更晚，就不可能在前方车队到达终点前追上它。这个判断把连续运动问题化成了时间大小比较，不需要逐秒模拟，也不需要维护车队速度。合并后的车队到达时间等于前方较慢车队的时间，也就是 lastTime 不变。

后车能否追上前队：
tBack <= tFront  -> 能追上，合并，车队时间仍是 tFront
tBack >  tFront  -> 追不上，新车队，时间更新为 tBack

四、为什么 lastTime 单调不降

扫描过程中，lastTime 记录“当前最靠后的已确定车队的到达时间”。每出现一个新车队，它一定是因为 t > lastTime，所以 lastTime 会变大。若 t <= lastTime，车辆并入前方车队，lastTime 不变。于是车队时间序列单调不降。

这个性质也解释了为什么有人用栈做：把位置升序或降序处理后，维护一个到达时间的单调结构。实际上按位置降序扫描时，只需要一个变量就够，因为后车只可能和最近的前方车队发生关系，而前方车队的有效时间正是当前最大时间。

当前车时间 t	与 lastTime 关系	动作	车队数
t <= lastTime	能追上	合并	不变
t > lastTime	追不上	新队	+1

五、为什么不能按位置升序直接扫

如果从远离终点的车开始扫，你还不知道它前方最终会形成什么车队。后面的判断依赖“前方车队的到达时间”，而这个信息只有从靠近终点到远离终点处理时才是已知的。升序也能做，但通常要用栈从后往前或在遍历结束后处理，容易绕。

例子 [0,3,5,8,10] 若从 0 开始，位置 0 的车时间 12，看起来是慢车队；但它前面位置 3 的车时间 3 会并入位置 5 的车队，而位置 0 追不上这个合并队。你必须先知道前方结构，才能判断当前车是否合并。降序扫描正好满足这个依赖方向。

依赖方向：
当前后车的归属 -> 取决于前方最近车队
所以处理顺序 -> 先前方，后后方

六、精度、边界和复杂度

到达时间要用浮点或分数比较，不能用整数除法。比如距离 5、速度 2 的时间是 2.5，整数除法会变成 2，可能错误合并车队。若担心浮点精度，可以比较分数：(target-pos1)/speed1 <= lastTime 在实现里用 double 通常已足够，严格场景可用交叉乘法。

边界包括没有车、只有一辆车、所有车速度相同、所有车最终合并、所有车都追不上。复杂度是 O(n log n) 排序加 O(n) 扫描，额外空间通常 O(n) 用来存 [position, speed]，也可以排序索引数组减少数据复制。

n=5 排序成本约 5log5，扫描 5 次
target=12, position=10, speed=2 -> time=(12-10)/2=1.0
target=12, position=3, speed=3  -> time=(12-3)/3=3.0

七、常见误区与追问

误区：按输入顺序扫描即可。 输入顺序不代表道路前后关系，必须按位置排序。
误区：后车更快就一定形成新车队。 更快通常意味着会追上前车，合并后反而不增加车队。
误区：用整数除法计算到达时间。 小数时间会被截断，导致合并判断错误。
追问：为什么 t <= lastTime 算合并？ 后车单独到终点不晚于前方车队，且起点在后，不能超车，所以会在终点前或终点处追上。
追问：能不能用栈？ 可以，把到达时间按位置顺序维护成单调栈；按位置降序时可压缩成一个 lastTime。
追问：如果允许超车怎么办？ 车队规则被破坏，每辆车可以独立到达，不能再用当前合并逻辑。

八、加强记忆

Car Fleet 的主线是“排序建立物理顺序，时间判断是否追上”。先按位置从近到远排，因为后车归属依赖前方车队；再计算每辆车到终点时间。t <= lastTime 表示会追上并入，t > lastTime 表示追不上开新队。把“从终点往回看”和“更晚才新队”这两个点记住，就不会被速度大小或输入顺序带偏。

简化版

详细版