853. Car Fleet

Medium

Description

有 n 輛車沿單線道往目的地 target 前進。每輛車有起始位置 position[i] 和速度 speed[i]。後方車追上前方車時會合併為一個車隊（以較慢車的速度行駛）。計算最終到達目的地的車隊數量。

Example:

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

Intuition#

核心思路：按位置從遠到近排序，計算每輛車到達終點的時間。若後方車比前方車更早到達，它會被前方車擋住、合併成同一車隊。

關鍵觀察：位置較前的車先被考慮（它不會被後方車加速），後方車到達時間 <= 前方車就會合併
計算每輛車到達 target 的時間：time = (target - position) / speed
從位置最遠的車開始掃描，若當前車的到達時間 <= 前一個車隊的到達時間，則合併；否則形成新車隊

Approaches#

1: 排序 + 線性掃描#

概念: 按位置降序排列，依序比較到達時間，計算車隊數
時間複雜度: O(n log n) - 排序
空間複雜度: O(n) - 排序使用的額外空間

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val n = position.size
        val cars = position.zip(speed).sortedByDescending { it.first }

        var fleets = 0
        var currentTime = 0.0

        for ((pos, spd) in cars) {
            val time = (target - pos).toDouble() / spd
            if (time > currentTime) {
                fleets++
                currentTime = time
            }
        }

        return fleets
    }
}

⭐2: Sort + Stack#

概念: 按位置降序排列，用堆疊維護車隊。將到達時間壓入堆疊，若當前時間 <= 棧頂時間，表示合併（不壓入）。最終堆疊大小即車隊數
時間複雜度: O(n log n) - 排序為瓶頸
空間複雜度: O(n) - 堆疊空間

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val n = position.size
        val cars = position.zip(speed).sortedByDescending { it.first }
        val stack = ArrayDeque<Double>()

        for ((pos, spd) in cars) {
            val time = (target - pos).toDouble() / spd
            if (stack.isEmpty() || time > stack.last()) {
                stack.addLast(time)
            }
        }

        return stack.size
    }
}

到達時間的比較必須用浮點數（Double），因為 (target - pos) / speed 可能不是整數。也要注意排序是按位置降序（離終點近的先處理），而非升序。

🔑 Takeaways#

Pattern: 碰撞/合併問題可以轉化為排序 + 時間比較，用 Stack 追蹤未合併的群組
關鍵技巧: 核心洞察是「前方車擋住後方車」——按位置排序後，只需比較到達時間。Stack 在此作為「保留不同車隊」的容器，本質上是一個遞增單調堆疊（時間遞增）