解題說明
Car Fleet II
題目描述:在無限長道路上,n 輛車排成一列,位置為 cars[i][0],速度為 cars[i][1](位置遞增,即後方車輛位置較小)。後車可以追上前車並形成車隊(速度採用前車速度)。計算每輛車追上前方車隊所需的時間,若永遠追不上則為 -1.0。回傳每輛車的追及時間陣列。
解題思路:從右向左掃描,使用單調棧。關鍵觀察:若車輛 i 能追上車輛 j(j 在 i 前方),但車輛 j 在被 i 追上之前已加入了更前方的車隊(速度已降至更慢),則 i 追上 j 的時間取決於 j 加入車隊前的速度。
從最右邊開始,對每輛車 i 計算追上前方車輛的時間:
- 維護單調棧,棧中元素為可能被追及的車輛索引,且其「被追及時間」單調遞增。
- 對車輛 i,計算追上棧頂車輛 j 的時間
t = (pos[j]-pos[i]) / (speed[i]-speed[j])(若speed[i] <= speed[j]則追不上,跳過)。 - 若
t小於等於棧頂的ans[j](或 ans[j] == -1),則 i 可以追上 j,時間為 t;否則說明 j 先被更前方的車輛「吸收」,繼續看棧中下一輛。 - 棧中彈出已確定不影響 i 的車輛,將 i 推入棧。
C++ 解法
複雜度分析
時間複雜度:O(n) 均攤 — 每輛車最多入棧一次、出棧一次,雖內層有 while 迴圈,但所有彈出操作合計不超過 n 次,整體線性。
空間複雜度:O(n) — 單調棧最多儲存 n 個索引。
虛擬碼
1. Initialize ans[0..n-1] = -1.0, empty stack stk.
2. For i from n-1 down to 0:
a. While stk not empty:
- j = stk.top().
- If speed[i] <= speed[j]: pop j (i can never catch j); continue.
- t = (pos[j] - pos[i]) / (speed[i] - speed[j]).
- If ans[j] < 0 or t <= ans[j]:
* ans[i] = t; break.
- Else: pop j (j already absorbed before i reaches it).
b. Push i onto stk.
3. Return ans.其他解法
方法一:暴力模擬 對每輛車 i,逐一計算追上前方每輛車 j 的時間,取最早的有效追及時間。時間 O(n^2),空間 O(1),適合 n 較小的情況(n ≤ 1000),無法通過本題最大規模(n = 10^5)。
方法二:優先隊列(事件驅動模擬) 計算所有相鄰車對的預計碰撞時間,加入優先隊列(最小堆)。按時間順序處理碰撞事件,更新受影響車輛的速度,再重新計算新的碰撞時間。時間 O(n log n),邏輯較複雜,需處理「碰撞後速度改變導致後續碰撞失效」的情況。
方法三:分治(Divide and Conquer) 將車輛分為左右兩半分別處理,再處理跨越中點的追及關係。時間 O(n log n),但不如單調棧直觀,競程中少見。
延伸思考
- 若道路長度有限(長度為 L),超過終點後車輛消失,如何修改算法處理此約束?
- 若每輛車有加速度(非勻速),追及時間的計算會變成二次方程,算法框架是否仍適用?
- 本題從右向左掃描的單調棧,與「下一個更大元素」(LeetCode 496)從右向左的單調棧有何結構上的相似之處?