LeetCode 853. 车队

2026-04-24 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 853. 车队

题意分析

若干辆车在同一条单向车道上朝同一个终点行驶，各自有起始位置和恒定速度。车道只有一条，不允许超车：快车追上慢车后只能贴在它后面，以慢车的速度一起前进，这一群车从此被称作一个车队。问所有车都抵达终点时，一共形成几个车队。

「不允许超车」是把物理模拟变成纯比较的关键。它保证了车与车的前后顺序永远不变，抵达终点的顺序就是初始位置的顺序，任何车都不可能绕到前车之前。

还有一条容易读漏的规则：恰好在终点处追上也算同一个车队。这直接决定了后面判定式该用严格大于还是大于等于。

约束里车辆数最多 $10^5$，位置互不相同且都小于终点，速度为正整数。规模允许排序，但不允许任何按时间步推进的模拟。

边界上要留意：只有一辆车时答案是 1；位置互不相同这一条免去了同位置的歧义；速度可以差异很大，时间的比较必须精确，不能被整数除法截断。

解法：排序 + 单调栈思想

核心思路

最直白的思路是模拟：让时间一点点往前走，不断检查谁追上了谁、谁被并进了哪个车队。这既要处理浮点的追及时刻，又要在合并后更新整队速度，实现复杂且容易漏掉链式合并（A 并入 B 之后 C 又并入 A）。

瓶颈在于模拟关心的是「过程」，而题目只问「结果」。跳过过程的突破口是这样一个观察：由于不能超车，如果只看某一辆车，忽略前方所有阻挡，它单独跑完全程需要的时间是 $t = (\text{target} - \text{position}) / \text{speed}$。这辆车实际抵达终点的时刻，一定不早于 $t$——被堵住只会更慢。

于是判定条件可以完全脱离过程：把车按位置从近到远（靠近终点的排在前）依次考察。对当前这辆车来说，它前方所有车里，实际抵达终点最晚的那个时刻，恰好等于这些车单独行驶时间的最大值（最慢的那辆决定了它所在车队的抵达时刻，且它前面的车不会拖慢它）。如果当前车单独跑的时间比这个最大值还大，说明即使一路畅通它也比前面所有车都晚到，永远追不上任何人，只能自立门户成为一个新车队；反之，它的单独时间不超过前方最晚抵达时刻，说明它必然在终点或终点之前撞上前方车队的尾巴，被吸收进去，不产生新车队。

由此得到扫描过程的不变量：按位置从大到小处理完若干辆车之后，maxTime 等于这些车中单独行驶时间的最大值，也就是这批车里最晚抵达终点的时刻；fleets 等于这批车已经形成的车队数。每读入一辆更靠后的车，只需要把它的单独时间和 maxTime 比一次大小：更大就 fleets 加一并抬高 maxTime，否则什么都不做。

注意判定必须用严格大于。时间相等意味着两车恰好在终点相遇，题目规定这算同一个车队，所以相等时不能新开车队。另外 maxTime 只在新开车队时被抬高——它是历史最大值，绝不能被后来更小的时间拉低，否则「前方最晚抵达时刻」这个语义就废了。

这个过程与单调栈同源：如果真的用一个栈从近到远压入各车的时间，并在新车时间不大于栈顶时把它丢弃，栈里剩下的就是严格递增的时间序列，栈的大小即答案。既然我们只关心栈的大小和栈顶，一个 maxTime 变量就足以替代整个栈。

解题步骤

先把 position 和 speed 按下标配成二元组。为什么必须配对：两个数组是按车辆下标一一对应的，只对其中一个排序会让位置和速度错配。

按位置降序排序，让最靠近终点的车排在最前。为什么是降序：判定依赖「当前车前方所有车的最晚抵达时刻」，从近到远扫描才能保证处理到某辆车时，它前方的车已经全部被统计进 maxTime。

令 fleets = 0、maxTime = 0，依次遍历排好序的车。为什么 maxTime 初值取 0：所有单独行驶时间都为正，第一辆车必定大于它而开出第一个车队，符合「最靠前的车永远是一个车队的头」。

对每辆车计算 time = (target - position) / speed，注意用浮点除法。为什么不能用整数除法：两辆真实时间不同的车可能被截断成同一个值，从而被错误地判成同一车队。

若 time > maxTime，则 fleets 加一并把 maxTime 更新为 time；否则跳过。为什么是严格大于：时间相等表示在终点处相遇，按题意属于同一个车队。为什么只在新车队时更新 maxTime：它的语义是历史最大值，被并入的车抵达时刻由前车决定，不能让它把上界拉低。

遍历结束返回 fleets。

以 target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] 走一遍：配对后按位置降序排成 $(10,2)$、$(8,4)$、$(5,1)$、$(3,3)$、$(0,1)$。初始 fleets = 0、maxTime = 0。

处理 $(10,2)$：单独时间 $(12 - 10) / 2 = 1.0$，大于 maxTime 的 0，开出第一个车队，fleets = 1，maxTime = 1.0。

处理 $(8,4)$：单独时间 $(12 - 8) / 4 = 1.0$，与 maxTime 相等而非大于，说明它恰好在终点追上前车，并入同一车队。fleets 仍为 1，maxTime 仍为 1.0。

处理 $(5,1)$：单独时间 $(12 - 5) / 1 = 7.0$，大于 1.0，它跑得比前面所有车都慢，永远追不上，自成新车队。fleets = 2，maxTime = 7.0。

处理 $(3,3)$：单独时间 $(12 - 3) / 3 = 3.0$，小于 7.0，说明它会在途中撞上那辆 7.0 的慢车，被并入。fleets 仍为 2，maxTime 保持 7.0（这里绝不能改成 3.0）。

处理 $(0,1)$：单独时间 $(12 - 0) / 1 = 12.0$，大于 7.0，最后这辆车谁也追不上，独立成队。fleets = 3，maxTime = 12.0。

遍历结束返回 3。对照实际过程：位置 10 和 8 的两车在终点合成一队；位置 5 的车速度只有 1，位置 3 的车虽然速度是 3 却会追上它，两者合成第二队；位置 0 的车速度也是 1，起步最靠后且不比前面快，独自成为第三队。

代码实现

class Solution {
    // 计算每辆车到终点的时间，若时间大于当前最大时间则形成新车队。
    public 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][0] = position[i];
            cars[i][1] = speed[i];
        }

        Arrays.sort(cars, (a, b) -> b[0] - a[0]);

        int fleets = 0;
        double maxTime = 0;
        for (int[] car : cars) {
            double time = (double) (target - car[0]) / car[1];
            if (time > maxTime) {
                fleets++;
                maxTime = time;
            }
        }

        return fleets;
    }
}

func carFleet(target int, position []int, speed []int) int {
    // 计算每辆车到终点的时间，若时间大于当前最大时间则形成新车队。
    n := len(position)
    cars := make([][2]int, n)
    for i := 0; i < n; i++ {
        cars[i] = [2]int{position[i], speed[i]}
    }

    sort.Slice(cars, func(i, j int) bool {
        return cars[i][0] > cars[j][0]
    })

    fleets := 0
    maxTime := 0.0
    for _, car := range cars {
        time := float64(target-car[0]) / float64(car[1])
        if time > maxTime {
            fleets++
            maxTime = time
        }
    }

    return fleets
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是车辆数。按位置排序是唯一的瓶颈；排序之后只做一次线性扫描，每辆车上只有一次除法和一次比较。

空间复杂度：$O(n)$，需要把位置和速度配对存进一个长度为 $n$ 的结构中再排序；扫描本身只用了 fleets 和 maxTime 两个标量，若允许原地重排输入则可降到排序自身的栈开销。

关键点总结

题目问「过程结束后的结果」而不是过程本身时，先找一个能脱离过程直接计算的量。这里就是「无阻挡时的单独行驶时间」，它把追及模拟彻底消掉了。

处理顺序要服务于判定所需的信息。判定依赖前方车辆的信息，所以必须从靠近终点的一端开始扫描；顺序反了，需要的信息还没被统计出来。

「历史最大值」型的变量只允许单向增长。被合并的元素不能拉低它，这一点在很多贪心扫描里都会成为隐蔽的错误来源。

相等即合并还是相等即分裂，务必回题面确认。本题「在终点相遇也算一个车队」直接决定了判定式取严格大于。

面试视角：主动点破这就是单调栈的坍缩形态——用栈维护严格递增的时间序列，答案是栈的大小，而我们只需要栈顶和大小，于是退化成一个变量。能说清这层关系，比只写出十行代码更能体现结构感。

面试视角：如果面试官关心浮点精度，可以给出无浮点写法——比较两辆车的时间改为交叉相乘，即用 $(\text{target} - p_i) \cdot s_j$ 与 $(\text{target} - p_j) \cdot s_i$ 的大小关系判定，全程整数运算，注意乘积用 64 位保存。

易错点总结

错误写法：按位置升序排序，从最远的车开始扫描。用例 target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] → 第一辆处理的是时间 12.0 的车，之后所有车的时间都不大于它，返回 1，正确答案是 3。

错误写法：用整数除法计算到达时间。用例 target = 10, position = [6,2], speed = [4,5] → 真实时间是 1.0 与 1.6，整除后都变成 1，后车被误判成在终点追上前车，返回 1，正确答案是 2。

错误写法：判定写成 time >= maxTime。用例 target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] → 时间同为 1.0 的两辆车被拆成两队，返回 4，正确答案是 3。

错误写法：每辆车都无条件更新 maxTime = time，而不是只在新开车队时更新。用例 target = 20, position = [10,6,2], speed = [2,7,6] → 三车的单独时间依次是 5.0、2.0、3.0，maxTime 被第二辆车拉低到 2.0，第三辆的 3.0 于是被误判为新车队，返回 2，正确答案是 1。

错误写法：maxTime 初始化成一个很大的值。用例任意输入 → 没有任何车的时间能超过它，一个车队都开不出来，返回 0。

错误写法：把 position 和 speed 分别排序而不是配对后整体排序。用例任意速度与位置不同序的输入 → 车与速度错配，算出的时间与任何真实车辆都不对应，结果无意义。

错误写法：认为速度快的车先到终点，据此判断车队归属。用例 target = 10, position = [0,8], speed = [10,1] → 后车速度是前车的十倍，但受阻于不能超车，最终并入前车，正确答案是 1，按速度判断会得到 2。

错误写法：用 32 位浮点保存时间。用例位置与速度都接近 $10^6$ 且两车时间极为接近的输入 → 尾数精度不足使两个本不相等的时间被判成相等，车队数偏小。

相似题目

题目	难度	考察点
739. 每日温度	中等	显式单调栈，要求每个位置的下一个更大元素的距离
496. 下一个更大元素 I	简单	单调栈配合哈希映射，在另一数组上查询结果
84. 柱状图中最大的矩形	困难	需要同时取左右两侧边界，栈中必须存下标而非数值
42. 接雨水	困难	单调栈按层结算面积，也可用双指针的对称贪心替代