LeetCode 853. 车队

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 快手
标签
数组 排序 栈 单调栈

题目描述

✅ 853. 车队

image-20260928225203179

image-20260928225203180

题意分析

所有车在同一条不能超车的道路上驶向目标位置。后车可以追上前车，追上后就受前方速度约束，与其作为同一车队继续行驶；即使恰好在终点追上，也算同一队。求到达目标时的车队数量。

车辆是否追得上同时取决于出发位置和速度，不能只比较谁更快。位置和速度必须始终按同一辆车配对，输入位置彼此不同且都在终点之前。

解法：排序 + 单调栈思想

核心思路

[!blue]

按位置从大到小处理，先看最靠近终点的车，再逐步加入它后面的车。这样前方所有车辆已经形成确定的车队，当前车首先可能碰到的就是其中最后一队，不需要向后预测其他尚未处理的车。

一辆车没有受到阻挡时的到达时间为 (target - position) / speed。用 maxTime 保存当前最靠后的已形成车队的到达时间；由于不允许超车，各个独立车队从前往后的到达时间必须严格递增，最后一队也就是已处理车队中到达最晚的一队。

若当前车的自由到达时间不大于 maxTime，它本来能比前队更早或同时到达，却不能穿过前队，因此必然在终点前或终点处追上，合并为同一队。追上后它必须跟随前队，不能让前队变快，所以 maxTime 保持不变。

若当前车的自由到达时间大于 maxTime，它无法在前队到达终点前追上，必须单独形成新队。新队到达更晚，更新 maxTime 为它的时间，供后续更靠后的车辆比较。这个单调关系使我们只需保留最后一个车队时间，而不必维护完整的栈。

计算时间必须保留小数，否则不同的真实到达时间可能被整数截断成相同值，误判能否合并。当前位置严格在终点前且速度为正，时间都大于零，所以初值 maxTime = 0 会正确建立第一支车队。

解题步骤

  1. 将每辆车的位置和速度组成一条记录，按位置降序排序。
  2. 初始化车队数为零、最后车队时间为零。
  3. 依次用浮点除法计算每辆车的自由到达时间。
  4. 只有当前时间严格大于已记录车队时间，才新增一队并更新时间；否则并入前队，保持时间不变。
  5. 返回车队总数。

代码实现

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;
    }
}

import "sort"

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)$，排序后只需一次线性扫描。
  • 空间复杂度：$O(n)$，保存位置与速度配对的记录数组，不改变原始两条输入数组。

关键点总结

[!green]

  • 从前向后处理，当前车只需与最近的前方车队比较到达时间。
  • 更早或同时自由到达都会合并，只有严格更晚才能形成独立车队。
  • 并入的快车不会加快前方车队，合并时不能降低记录时间。
  • 独立车队到达时间严格递增，因此只存最后一个时间即可。

易错点总结

[!yellow]

  • 分别排序位置和速度，会丢失同一辆车的对应关系。
  • 使用整数除法，会截掉关键的小数差异，错误合并本来分离的车队。
  • 将到达时间相等也算新队，违反终点相遇仍合并的规则。
  • 每处理一辆车都覆盖记录时间，会让已经形成的慢车队被后来的快车错误加速。
  • 从远离终点的一侧开始，却继续沿用当前只看前队的规则，比较对象尚未形成，不能保证正确性。

相似题目

题目 难度 关联与区别
1776. 车队 II 困难 同样按位置分析前后车辆追赶，原题求每辆车首次碰撞时间，本题只按到终点的时间合并车队。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/44245775
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！