Medium

题目描述

有 n 辆车在给定的起始里程 0 处，前往目标里程 target。

给你两个长度为 n 的整数数组 position 和 speed，其中 position[i] 是第 i 辆车的起始里程，speed[i] 是第 i 辆车的速度（单位：英里/小时）。

一辆车不能超过另一辆车，但可以追上并与之并排行驶，此时以较慢车辆的速度行驶。

车队是指单独一辆车或一组并排行驶的车辆。车队的速度是车队中任意一辆车的最小速度。

如果一辆车在目标里程处追上了车队，它仍然被认为是该车队的一部分。

返回到达目的地的车队数量。

示例 1：

输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10（速度 2）和 8（速度 4）开始的车在 12 处相遇，形成一个车队。
从 0（速度 1）开始的车没有追上任何其他车，因此它自己形成一个车队。
从 5（速度 1）和 3（速度 3）开始的车在 6 处相遇，形成一个车队，以速度 1 行驶直到目标。

示例 2：

输入：target = 10, position = [3], speed = [3]
输出：1
解释：只有一辆车，因此只有一个车队。

示例 3：

输入：target = 100, position = [0,2,4], speed = [4,2,1]
输出：1
解释：
从 0（速度 4）和 2（速度 2）开始的车在 4 处相遇，形成一个车队。
从 4（速度 1）开始的车行驶到 5。
然后，在 4 处的车队（速度 2）和在位置 5 处的车（速度 1）在 6 处相遇，形成一个车队，以速度 1 行驶直到目标。

提示：

  • n == position.length == speed.length
  • 1 <= n <= 10^5
  • 0 < target <= 10^6
  • 0 <= position[i] < target
  • position 的所有值都是唯一的
  • 0 < speed[i] <= 10^6

解题思路

这道题的关键思路是理解车队的形成规律：

  1. 车辆不能超车，只能跟随前面较慢的车
  2. 需要计算每辆车到达终点的时间，如果后面的车能在终点前追上前面的车，它们就会形成车队

核心思路：

  • 按位置从大到小排序（离终点近的在前）
  • 计算每辆车到达终点的时间：time = (target - position) / speed
  • 从最接近终点的车开始遍历，如果当前车的到达时间小于等于前面车的到达时间，说明会被前面的车阻挡，形成车队
  • 使用单调栈或简单遍历来统计车队数量

解法选择：

  1. 排序 + 单调栈：按位置排序后，用栈维护车队的到达时间
  2. 排序 + 贪心：更简洁的方法，直接比较到达时间

推荐使用贪心解法，代码更简洁且易理解。

代码实现

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, int>> cars;
        
        // 将位置和速度配对
        for (int i = 0; i < n; i++) {
            cars.push_back({position[i], speed[i]});
        }
        
        // 按位置从大到小排序
        sort(cars.begin(), cars.end(), greater<pair<int, int>>());
        
        int fleets = 0;
        double prevTime = 0;
        
        // 计算每辆车到达终点的时间
        for (auto& car : cars) {
            double time = (double)(target - car.first) / car.second;
            // 如果当前车的时间大于前面车的时间，说明形成新车队
            if (time > prevTime) {
                fleets++;
                prevTime = time;
            }
        }
        
        return fleets;
    }
};

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # 将位置和速度配对并按位置从大到小排序
        cars = sorted(zip(position, speed), reverse=True)
        
        fleets = 0
        prev_time = 0
        
        # 计算每辆车到达终点的时间
        for pos, spd in cars:
            time = (target - pos) / spd
            # 如果当前车的时间大于前面车的时间，说明形成新车队
            if time > prev_time:
                fleets += 1
                prev_time = time
                
        return fleets

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        var cars = new (int pos, int spd)[n];
        
        // 将位置和速度配对
        for (int i = 0; i < n; i++) {
            cars[i] = (position[i], speed[i]);
        }
        
        // 按位置从大到小排序
        Array.Sort(cars, (a, b) => b.pos.CompareTo(a.pos));
        
        int fleets = 0;
        double prevTime = 0;
        
        // 计算每辆车到达终点的时间
        foreach (var car in cars) {
            double time = (double)(target - car.pos) / car.spd;
            // 如果当前车的时间大于前面车的时间，说明形成新车队
            if (time > prevTime) {
                fleets++;
                prevTime = time;
            }
        }
        
        return fleets;
    }
}

var carFleet = function(target, position, speed) {
    const n = position.length;
    const cars = [];
    
    // 将位置和速度配对
    for (let i = 0; i < n; i++) {
        cars.push([position[i], speed[i]]);
    }
    
    // 按位置从大到小排序
    cars.sort((a, b) => b[0] - a[0]);
    
    let fleets = 0;
    let prevTime = 0;
    
    // 计算每辆车到达终点的时间
    for (const [pos, spd] of cars) {
        const time = (target - pos) / spd;
        // 如果当前车的时间大于前面车的时间，说明形成新车队
        if (time > prevTime) {
            fleets++;
            prevTime = time;
        }
    }
    
    return fleets;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，主要为排序的时间复杂度
空间复杂度O(n)，用于存储车辆信息的额外空间

相关题目