有
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
TIP
核心思路：按位置從遠到近排序，計算每輛車到達終點的時間。若後方車比前方車更早到達，它會被前方車擋住、合併成同一車隊。
- 關鍵觀察：位置較前的車先被考慮（它不會被後方車加速），後方車到達時間 <= 前方車就會合併
- 計算每輛車到達
target的時間：time = (target - position) / speed - 從位置最遠的車開始掃描，若當前車的到達時間 <= 前一個車隊的到達時間，則合併；否則形成新車隊
Approaches
1. Sort + Linear Scan — O(n log n) / O(n)
- Idea: 按位置降序排列，依序比較到達時間，計算車隊數
- Time:
O(n log n)- 排序 - Space:
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)
- Idea: 按位置降序排列，用堆疊維護車隊。將到達時間壓入堆疊，若當前時間 <= 棧頂時間，表示合併（不壓入）。最終堆疊大小即車隊數
- Time:
O(n log n)- 排序為瓶頸 - Space:
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
}
}WARNING
到達時間的比較必須用浮點數（Double），因為 (target - pos) / speed 可能不是整數。也要注意排序是按位置降序（離終點近的先處理），而非升序。
🔑 Takeaways
- Pattern: 碰撞/合併問題可以轉化為排序 + 時間比較，用 Stack 追蹤未合併的群組
- Key trick: 核心洞察是「前方車擋住後方車」——按位置排序後，只需比較到達時間。Stack 在此作為「保留不同車隊」的容器，本質上是一個遞增單調堆疊（時間遞增）