1.题目基本信息

1.1.题目描述

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。

给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。

车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。

即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。

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

1.2.题目地址

https://leetcode.cn/problems/car-fleet/description/

2.解题方法

2.1.解题思路

单调栈+排序。根据position和speed数组计算每个车辆到达终点需要的时间数组times，并将times按position从小到大进行排序。不妨设所有的车辆都是从左到右走，则如果左边的车辆所需时间比右边的车辆长，则这俩车辆不可能形成车队，否则可以形成车队，且在左边的车追上右边的车后，左边的车与右边的车相同速度进行行驶。所以可以逆向遍历times，从times末尾弹出time1，记车辆为车辆A，如果time1>=times[-1]，则当前末尾车辆可以追上车辆A，更新末尾车辆时间为time1，如果time1<times[-1]，则车辆A所用时间可以形成车队，车队数+1

3.解题代码

python代码

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # 思路：单调栈+排序。根据position和speed数组计算每个车辆到达终点需要的时间数组times，并将times按position从小到大进行排序。不妨设所有的车辆都是从左到右走，则如果左边的车辆所需时间比右边的车辆长，则这俩车辆不可能形成车队，否则可以形成车队，且在左边的车追上右边的车后，左边的车与右边的车相同速度进行行驶。所以可以逆向遍历times，从times末尾弹出time1，记车辆为车辆A，如果time1>=times[-1]，则当前末尾车辆可以追上车辆A，更新末尾车辆时间为time1，如果time1<times[-1]，则车辆A所用时间可以形成车队，车队数+1
        times = [(target - p) / s for p, s in sorted(zip(position, speed))]
        times = [inf] + times
        result = 0
        while len(times) > 1:
            time1 = times.pop()
            if time1 >= times[-1]:
                times[-1] = time1
            else:
                result += 1
        return result

4.执行结果