0853. Car Fleet

题目信息

题号:

0853

难度:

Medium

主题:

车辆运动、追赶、车队计数

原题:

LeetCode 0853

重点:

车辆不能超车;后车追上前车后以较慢速度共同前进,同一时刻在目标处相遇也算一个车队

题目重述

有 n 辆车沿同一直线向里程位置 target 行驶。等长数组 position 和 speed 分别表示每辆车的初始位置和恒定速度,所有初始位置互不相同且都小于目标。

车辆不能超车。若一辆较快的后车追上前车,它们从此组成一个车队,并以车队中最慢车辆的速度共同前进;多个车辆或车队可以继续合并。若后车恰好在目标位置追上前车,也视为同一车队。请返回最终到达目标的车队数量。

n == position.length == speed.length,1 <= n <= 10^5,1 <= target <= 10^6;0 <= position[i] < target 且所有位置互不相同,1 <= speed[i] <= 10^6。

自建示例

后方车辆在目标前追上:

输入:target = 10, position = [0,4,7], speed = [2,1,1]
输出:2
解释:位置 0 的车会在位置 8 追上位置 4 的车,二者组成一个车队;位置 7 的车更早单独到达目标,因此共有两个车队。

只有一辆车:

输入:target = 8, position = [6], speed = [1]
输出:1
解释:车辆数量达到题目允许的最小值。唯一车辆不可能与其他车辆合并,因此自身构成一个车队。