What is the key pattern for solving the Car Fleet problem?

The Car Fleet problem is best solved using stack-based state management, where cars are processed in the order of their starting positions, and fleets are formed based on their times to reach the target.

How do I calculate the time for each car to reach the target?

To calculate the time for each car to reach the target, use the formula `(target - position[i]) / speed[i]`, where `position[i]` is the car’s starting point, and `speed[i]` is its speed.

What happens if two cars reach the target at the same time?

If two cars reach the target at the same time, they form a fleet and are counted as one, meaning you should only count the number of distinct fleets formed.

Can I solve this problem with a brute force approach?

A brute force approach could be inefficient as it would require simulating each car's movement, potentially leading to a time complexity greater than O(n log n). Sorting and stack management offer a more optimal solution.

What is the time complexity of the Car Fleet problem?

The time complexity of the solution is O(n log n), where n is the number of cars, because sorting is the most computationally expensive step.

#853

Medium

auto_awesome栈·状态

LeetCode 题解工作台

车队

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。一辆车永远不会超过前面的另一辆…

数组栈排序单调栈

题目描述

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

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

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

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

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

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

示例 1：

输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

输出：3

解释：

从 10（速度为 2）和 8（速度为 4）开始的车会组成一个车队，它们在 12 相遇。车队在 target 形成。
从 0（速度为 1）开始的车不会追上其它任何车，所以它自己是一个车队。
从 5（速度为 1）和 3（速度为 3）开始的车组成一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

示例 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 移动直到它到达 target。

提示：

n == position.length == speed.length
1 <= n <= 10⁵
0 < target <= 10⁶
0 <= position[i] < target
position 中每个值都不同
0 < speed[i] <= 10⁶

lightbulb

解题思路

方法一：排序

我们将车辆按照位置降序排序，这样我们只需要比较相邻两辆车的到达时间即可。

我们初始化一个变量 $pre$ 表示上一辆车到达终点的时间，如果当前车辆到达终点的时间大于 $pre$ ，说明当前车辆无法追上前面的车辆，因此需要另外开一个车队，否则当前车辆会与前面的车辆组成一个车队。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是车辆的数量。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        idx = sorted(range(len(position)), key=lambda i: position[i])
        ans = pre = 0
        for i in idx[::-1]:
            t = (target - position[i]) / speed[i]
            if t > pre:
                ans += 1
                pre = t
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of stack-based state management and how it can be used to simulate the formation of car fleets.
question_mark
Assess whether the candidate can explain the key concept of cars catching up and joining fleets without overtaking.
question_mark
Evaluate the candidate’s ability to relate sorting and time calculations to the problem's logic, ensuring efficient fleet tracking.

warning

常见陷阱

外企场景

error
Failing to sort the cars correctly, which would lead to incorrect fleet grouping.
error
Misunderstanding the concept of fleet formation and incorrectly counting cars that are part of the same fleet.
error
Not accounting for cars that reach the target at the same time, which would result in overcounting fleets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if cars can overtake each other? This would change the approach as fleet formation rules would be different.
arrow_right_alt
What if the target is at the maximum boundary? This tests whether the solution can handle large input sizes efficiently.
arrow_right_alt
What if some cars start at the same position? This would require handling cases where multiple cars start from the same point but have different speeds.

help

常见问题

外企场景

继续练习

#769 最多能完成排序的块 #768 最多能完成排序的块 II #975 奇偶跳