0853. 车队

ITCharge大约 3 分钟

---

0853. 车队

标签：栈、数组、排序、单调栈
难度：中等

题目链接

0853. 车队 - 力扣

题目大意

描述：

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

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

一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。
车队是指并排行驶的一辆或几辆汽车。车队的速度是车队中「最慢」的车的速度。

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

要求：

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

说明：

$n == position.length == speed.length$ 。
$1 \le n \le 10^{5}$ 。
$0 \lt target \le 10^{6}$ 。
$0 \le position[i] \lt target$ 。
$position$ 中每个值都「不同」。
$0 \lt speed[i] \le 10^{6}$ 。

示例：

示例 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
解释：只有一辆车，因此只有一个车队。

解题思路

思路 1：排序 + 单调栈

这道题的关键是理解车队的形成：后面的车如果能在到达终点前追上前面的车，它们就会形成车队，以较慢的速度行驶。

算法步骤：

将车按照位置从大到小排序（从离终点近到远）。
计算每辆车到达终点所需的时间。
使用单调栈（或变量）维护车队：
- 从离终点最近的车开始遍历。
- 如果当前车的到达时间大于栈顶车队的到达时间，说明它无法追上前面的车队，形成新的车队。
- 否则，它会追上前面的车队，合并为一个车队。

思路 1：代码

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # 将车按位置从大到小排序
        cars = sorted(zip(position, speed), reverse=True)
        
        # 单调栈，存储每个车队到达终点的时间
        stack = []
        
        for pos, spd in cars:
            # 计算当前车到达终点的时间
            time = (target - pos) / spd
            
            # 如果栈为空，或当前车无法追上前面的车队，形成新车队
            if not stack or time > stack[-1]:
                stack.append(time)
            # 否则，当前车会追上前面的车队，合并（不需要操作）
        
        # 栈的大小就是车队数量
        return len(stack)

思路 1：复杂度分析

时间复杂度： $O(n \log n)$ ，其中 $n$ 是车的数量。排序需要 $O(n \log n)$ ，遍历需要 $O(n)$ 。
空间复杂度： $O(n)$ ，需要存储排序后的车辆信息和栈。