友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
853. 车队
在一条单行道上，有 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 <= 105 -
0 < target <= 106 -
0 <= position[i] < target -
position中每个值都 不同 -
0 < speed[i] <= 106
思路分析
将车按照位置排序，然后从后向前计算汽车的耗时，当后一辆车的耗时大于前一辆车的耗时，就可以追上前车，则就可以组成一个车队。追不上，则无法组成车队。
| 从左向右计算，左边的快车会被右边的慢车挡住路，所以从右向左计算更简单。 |
看题解，单调栈也是一个解法：
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-08 22:38:10
*/
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) {
cars[i] = new int[]{position[i], speed[i]};
}
Arrays.sort(cars, Comparator.comparingInt(a -> a[0]));
int result = n;
float ftarget = 0.0F + target;
float time = (ftarget - cars[n - 1][0]) / cars[n - 1][1];
for (int i = n - 2; i >= 0; i--) {
int[] car = cars[i];
float temp = (ftarget - car[0]) / car[1];
if (temp <= time) {
result--;
} else {
time = temp;
}
}
return result;
}