1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if (position.length == 0) {
            return 0;
        }
        double[][] posTravelTime = new double[position.length][2];
        for (int i = 0; i < position.length; i++) {
            posTravelTime[i][0] = (double) position[i];
            posTravelTime[i][1] = ((double) (target - position[i])) / speed[i];
        }
        Arrays.sort(posTravelTime, (a, b) -> Double.compare(b[0], a[0]));
        int ans = 1;
        double currFleetTimeBound = posTravelTime[0][1];
        for (int i = 1; i < posTravelTime.length; i++) {
            if (posTravelTime[i][1] <= currFleetTimeBound) {
                continue;
            } else {
                ans += 1;
                currFleetTimeBound = posTravelTime[i][1];
            }
        }
        return ans;
    }
}

大致思路就是我们先算出来每个car到达目的地需要的时间是多少, 然后再把各个car按照距离目的地的距离由近到远来排序. 首先第一个car(也就是距离target最近的那个)肯定自己构成一个fleet, 后面的下一个car如果到达目的地需要的时间小于等于第一个car到达目的地的时间, 那么这个car就能追上第一个car, 于是构成fleet. 类似地, 后面的car如果到达目的地的时间也是小于第一个car到达目的地的时间, 那么该car的速度是大于等于第2个car的速度的, 所以也会在到达目的地前和第1个car合体(可能先和第2个car合体, 再和第1个car合体). 以此类推. 直到我们遇到一种情况就是有个car需要到达target的时间大于第一个car到达target的时间的时候, 该car就不能和之前的car合并了, 于是此时它自己又构成一个fleet, 我们让ans + 1.

这道题很有意思的就是开始时我们把ans初始化为多少? 我当时想的是, ans初始化为0, 等找到一个car不能合体的时候, 该car之前就构成一个fleet, 此时让ans + 1. 但是如果一直到数组结束都找不到这样的car呢? 那岂不是就永远加不上1了. 于是我想的是, 当有car追不上时, 它自己新开一个fleet, 此时再 + 1, 虽然也是遇到追不上的car时让ans + 1, 但是这里的1对应的是这个新car形成的fleet, 而非对应该car之前的car形成的fleet. 那此时该如何初始化ans呢? 按照我们之前的做法, 假设第0个元素之前还有元素, 并且到第0个元素的时候赶不上了之前的car, 那么此时它自己构成一个fleet, 我们让ans + 1. 于是此时初始化ans为是比较合适的, 如果后续能合并, 我们让ans维持在1, 如果不能合并, 那我们让ans + 1对应这个不能和前面car合并的car新构成的fleet.

时间复杂度: O(nlogn)
空间复杂度: O(n)