題目

• 概述：N輛車沿著一條車道駛向位于target英里之外的共同目的地，每輛車i以恒定的速度speed[i]從初始位置position[i]沿車道駛向目的地，當(dāng)一輛車追上前一車隊時，它的速度會與前一輛車相同，且這輛車和前一輛車構(gòu)成一個車隊（一輛車也是一個車隊），問會有多少車隊到達(dá)目的地

  到目的地的一瞬間才趕上前一輛車也構(gòu)成一個車隊

• 輸入：

  1. target：終點位置，范圍[0, 10^6]
  2. position數(shù)組：車的初始位置（各不相同，且都是小于target的自然數(shù)）
  3. speed數(shù)組：車的速度，速度范圍(0, 10^6]
  4. 車的數(shù)量[0, 10^4]

• 輸出：到達(dá)目的地時的車隊數(shù)量

• 出處：https://leetcode-cn.com/problems/car-fleet/

思路

• 由于需要暫存初始位置離終點較遠(yuǎn)的車輛信息以判斷之后能否追上與初始位置離終點較近的車輛，所以考慮用棧實現(xiàn)

• 將車輛按照初始位置進(jìn)行排序

• 將第一輛車入棧

• 遍歷之后的車輛，若棧頂車隊不能在終點前追上當(dāng)前車輛，則將當(dāng)前車輛入棧

• 遍歷之后的車輛：

  1. 若棧頂車隊不能在終點前追上當(dāng)前車輛，則將當(dāng)前車輛入棧
  2. 若棧頂車隊能在終點前追上當(dāng)前車輛，棧頂車隊出棧，若此時棧為空，則將當(dāng)前車輛入棧，否則重復(fù)

• 最終棧中的車輛個數(shù)即為達(dá)到目的地時的車隊數(shù)量

  特別注意：兩個int型相乘可能會溢出，要將其中一個int型強(qiáng)轉(zhuǎn)為long型，而不是乘完再強(qiáng)轉(zhuǎn)就已經(jīng)溢出了

代碼

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if (position.length == 0) {
            return 0;
        }
        
        Car[] cars = new Car[position.length];
        for (int i = 0; i < position.length; ++i) {
            cars[i] = new Car(position[i], speed[i]);
        }
        Arrays.sort(cars, (car1, car2) -> car1.position - car2.position);
        
        LinkedList<Car> stack = new LinkedList<>();
        stack.push(cars[0]);
        for (int i = 1; i < position.length; ++i) {
            while (true) {
                if (stack.peek().slower(cars[i], target)) {
                    stack.push(cars[i]);
                    break;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(cars[i]);
                        break;
                    }
                }
            }
        }
        
        return stack.size();
    }
    
    private class Car {
        int position;
        int speed;
        Car(int position, int speed) {
            this.position = position;
            this.speed = speed;
        }
        
        boolean slower(Car car, int target) {
            if (car.speed >= speed) {
                return true;
            } else {
                // strong rotation one, not both
                return (long)(car.position - position) * car.speed > (long)(target - car.position) * (speed - car.speed);
            }
        }
    }
}