Car Fleet
汽车沿着一条单车道公路驶向里程标记为 target 的位置。汽车 i 从 position[i] 里程处出发，以每小时 speed[i] 英里的速度行驶。汽车不能超车：追上较慢汽车的汽车会停在它后面，从此两辆车以较慢的速度一起行驶，组成一个车队。
单辆汽车也算一个车队。汽车恰好在目的地追上车队时，也会加入车队。返回抵达目的地的车队数量。
函数
- targetinteger
- 每辆车都驶向的那一英里
- positioninteger-array
- 每辆车的起始里程
- speedinteger-array
- 每辆车的速度，单位为英里/小时
- 返回值integer
- 到达目的地的舰队数量
约束条件
n == position.length == speed.length1 ≤ n ≤ 1041 ≤ target ≤ 1060 ≤ position[i] < target1 ≤ speed[i] ≤ 106- 所有位置都不同。
示例
- 输入
- target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
- 输出
- 2
- 解释
- 单独行驶时，位于第 17、14、8 和 2 英里的汽车分别需要 3、2、3 和 3 小时，所以位于第 14 英里的汽车会追上位于第 17 英里的汽车，另外两辆会在第 20 英里处追上它们。位于 0 英里的汽车需要 10 小时，会独自到达。
- 输入
- target = 9position = [0, 4, 7]speed = [1, 2, 3]
- 输出
- 3
- 解释
- 里程为 7、4 和 0 的汽车分别需要 2/3、5/2 和 9 小时。每辆车都会比它前面的车晚到，所以没有车会追上其他车：
3个车队。
- 输入
- target = 10position = [3]speed = [5]
- 输出
- 1
- 解释
- 路上的一辆车就是一支车队。
进阶
这些位置都是小于 target 的整数。你能否在 O(n + target) 时间内统计车队数量，而不使用比较排序？
提示
逐个打开提示，每个都会多透露一点。
汽车的顺序永远不会改变。对于每辆汽车，算一算如果道路上没有其他车辆，它会在什么时候到达目的地。是什么决定了它能否追上前面的汽车？
从离目的地最近的汽车开始，向后移动。如果一辆汽车到达目的地的时间不晚于前面的车队，它就会加入该车队；否则，它会形成一个新的车队。
按位置从大到小排序，并将车队放在一个栈中，最新的车队放在顶部。使用 64 位整数比较时间
d1/s1和d2/s2，也就是比较d1 × s2和d2 × s1。
题解
在同一条车道上，汽车的顺序永远不会改变，决定一切的是每辆车单独行驶时的到达时间：(target - position[i]) / speed[i]。从距离目的地最近的汽车开始，向后依次查看。只有当一辆车的到达时间严格晚于前方车队时，它才会组成一支新的车队。
检查前方的每辆车
结果正确，但无法在最大的测试中运行完毕
思路
当车队中每辆位于它前方的车单独到达的时间都严格早于它时，这辆车才会领跑车队。如果前方有车到达得不比它早，你的车就会在目的地前追上那辆车或它所在的车队。如果前方所有车都到得更早，就没有车能挡住它，因为车队的到达时间是车队中各辆车单独到达时间的最大值。通过交叉相乘精确比较时间，统计领跑的车辆。
每辆车都要扫描全部 n 辆车：当 n = 10^4 时，需要检查 10^8 次。
算法
- 设置
fleets = 0。 - 对于每辆车
i，查看所有满足position[j] > position[i]的车辆j。 - 如果存在某个
j满足(target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j]，则车辆i会被追上：跳过它。 - 否则，车辆
i领头组成一个车队：将fleets加 1。 - 返回
fleets。
def carFleet(target, position, speed):
n = len(position)
fleets = 0
for i in range(n):
dist = target - position[i]
caught = False
for j in range(n):
# Car j is ahead and would not arrive before car i: car i catches it.
# (target - position[j]) / speed[j] >= dist / speed[i], without division.
if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
caught = True
break
if not caught:
fleets += 1
return fleets按位置排序并堆叠舰队
思路
按位置排序，离目的地最近的车辆排在前面。当前车辆前面的车，恰好是已经看过并且已经组成车队的车辆。把车队存放在栈中，每个车队记录其最前面车辆的距离和速度，这决定了车队的到达时间。
只需要关注栈顶。每次入栈的车队到达时间都严格晚于它下方的车队，因此时间从栈底到栈顶递增；而且晚于栈顶，就意味着晚于前面的所有车辆。
按顺序看，示例 1 中的车辆位于 17、14、8、2 和 0，距离除以速度分别为 3/1, 6/3, 12/4, 18/6, 20/2。将 (3, 1) 入栈。位于 14 的车辆会加入，因为 6 × 1 > 3 × 3 不成立。位于 8 的车辆到达时间相同，12 × 1 = 3 × 4，因此会加入，位于 2 的车辆也一样。对于位于 0 的车辆，20 × 1 > 3 × 2：入栈。
算法
- 按位置对汽车索引排序，位置最大的排在前面。
- 从一个空的车队栈开始。
- 对于每辆汽车，计算
dist = target - position[i]。 - 如果栈为空，或者
dist × topSpeed > topDist × speed[i]，就将(dist, speed[i])入栈；否则，这辆汽车加入栈顶的车队。 - 返回栈的大小。
def carFleet(target, position, speed):
# Visit the cars from the one closest to the target backward.
order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
# One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
stack = []
for i in order:
dist, spd = target - position[i], speed[i]
# dist / spd > top_dist / top_spd, compared without division:
# this car arrives after the fleet ahead, so it never catches it.
if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
stack.append((dist, spd))
return len(stack)
易错点和边界情况
- 把刚好相等的情况算作新的车队。示例 1 中位于 8 英里和 2 英里处的汽车会在 20 英里处与车队相遇并加入车队。只有时间严格更晚时才推入。
- 叉积溢出。
10^6 × 10^6 = 10^12无法用 32 位表示：在 Java、C、C++、C# 和 Rust 中，乘法前先扩展到 64 位；在 R 中，使用双精度数。 - 排序方向错误。从离目的地最远的汽车开始，会将每辆汽车与它后面的汽车进行比较，而后面的汽车永远无法阻挡它。
- 单独对
position排序。对索引或（位置、速度）对进行排序，确保每个速度都与对应的汽车保持配对。
常见问题3
Car Fleet 的时间复杂度是多少？
按位置排序需要 O(n log n)，使用栈遍历需要 O(n)，因此总时间复杂度为 O(n log n)，空间复杂度为 O(n)。逐一检查每辆车前面的所有车辆需要 O(n²)。
为什么 Car Fleet 要使用栈？
如何在不使用浮点数的情况下比较到达时间？
到达时间是 dist / speed。由于速度为正，d1 / s1 > d2 / s2 当且仅当 d1 × s2 > d2 × s1。两边都是不超过 10^12 的整数，因此用 64 位类型计算，比较结果是精确的，无需考虑舍入。
def carFleet(target, position, speed):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
target = 20 position = [14, 2, 8, 17, 0] speed = [3, 6, 4, 1, 2]
预期输出
2