853. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Explanation:

• The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
• The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
• The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2:

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

There is only one car, hence there is only one fleet.

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Explanation:

• The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
• Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Constraints:

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• All the values of position are unique.
• 0 < speed[i] <= 106

Solution:

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]){ // 汽车的位置
                return b[0] - a[0]; // 表示按位置进行降序排序
                // 这个排序逻辑让位置更靠近目标的汽车优先处理
            }else{// 位置相同
                return a[1] - b[1];// 汽车的素的进行比较
                // 表示按照速度升序排序, 也就是速度较慢的会排在前面
            }
        });

        for (int i = 0; i < position.length; i++){
            pq.add(new int[]{position[i], speed[i]});
        }

        Stack<Double> stack = new Stack<Double>();
        // 初始化一个栈, 用于存储每辆车(或车队)到达目标所需的时间

        while(!pq.isEmpty()){
            int arr[] = pq.poll();
            double reach = (target - arr[0]) / (double) arr[1];
            // 计算这辆车达到目标所需的时间. 这是通过用目标位置减去车位置, 然后除以车速

            if (stack.isEmpty() || stack.peek() < reach){
                stack.add(reach);
            }
            // 栈用于跟踪每个车队的领头车到达目标所需的时间
            // 如果栈是空的(这表示第一辆被处理的车) 或者栈顶元素(即上衣额车队的到达时间)
            // 小于当前车的reach时间, 那么这辆车将不会赶上前面的车队, 并形成一个新的车队.
            // 这种情况下, 将reach 时间压入栈中
        }

        return stack.size();s
    }
}

// TC: O(nlogn)
// SC: O(n)