題目描述:有多輛車在一條單向道路上行駛,給定每輛車的起始位置 position[i] 和速度 speed[i],以及目標終點 target。若一輛較快的車追上前方較慢的車,它們會形成一個「車隊」並以較慢的速度一同抵達終點。回傳抵達終點時共形成幾個車隊。
解題思路:關鍵觀察:只有前方的車才能阻擋後方的車。因此先按位置由大到小排序(靠近終點的車優先),計算每輛車單獨到達終點所需時間 time[i] = (target - position[i]) / speed[i]。使用堆疊(或直接比較):若後方車所需時間 ≤ 前方車(堆疊頂端)所需時間,表示後方車會追上前方車並合併為同一車隊;否則後方車形成新車隊。堆疊大小即為最終車隊數。
時間複雜度:O(n log n) — 排序主導,之後的線性掃描為 O(n)。
空間複雜度:O(n) — 儲存排序後的 (position, speed) 配對及堆疊,最壞情況下 n 輛車各為獨立車隊。
1. Create list of (position, speed) pairs 2. Sort by position in descending order (closest to target first) 3. Initialize empty stack for arrival times 4. For each car (pos, spd) in sorted order: a. Compute time = (target - pos) / spd b. If stack is empty OR time > stack.top(): push time (new fleet) c. Else: car merges with fleet ahead (do nothing) 5. Return stack size
直接計數(不使用堆疊) O(n log n):排序後用一個變數 maxTime 追蹤目前最慢車隊的到達時間。若當前車的到達時間超過 maxTime,則形成新車隊並更新 maxTime。邏輯等價且省去堆疊資料結構,只需 O(1) 額外空間。
模擬法 O(n²):直接模擬所有車輛的行進過程,偵測追及事件。概念直觀但時間複雜度較差,不適用於大輸入。