題幹與適用場景
這是一道帶資源限制的區間貪心題。車輛只能在已經經過的站點取油，油量決定下一次能否越過更遠位置；目標是最少加油站次數，不是總油量最少。面試中要同時說明可達性、延遲決策、最大堆不變量與最後一段到終點的邊界。
面試官考察什麼
- 能否把「油量不足時才加油」轉成延遲貪心。
- 能否證明從已經過站點取最大油量不會增加最優次數。
- 能否正確處理起點、終點、同位置站點與不可達情況。
- 能否給出 O(n log n) 時間、O(n) 空間的實作，並解釋堆操作。
回答前需要釐清的問題
確認站點是否嚴格按位置遞增、同一位置是否可能有多個站點、油量是否為非負整數，以及是否把目標點視為可加油站。也要確認輸入規模與整數範圍，避免固定寬度整數溢位。題目預設車輛在位置 0 出發，經過某站後才可使用該站燃油。
30 秒回答框架
按位置掃描站點，把經過站點的燃油放入最大堆。每走到下一站或終點，就從目前燃油扣除距離；若燃油為負，表示必須從已經過站點補油，反覆彈出最大值並增加次數。堆為空仍無法到達就回傳 -1。每次補油都選擇最大歷史油量，等價於在當前被迫增加一次停止時讓可達距離增加最多，因此不會劣於其他選擇。
分步驟深入解答
1. 建立可達性不變量
掃描到位置 p 時，堆保存所有位置不超過 p 的站點油量，fuel 是尚未使用的燃油。若燃油小於零，不可能繼續向前，必須從堆中選擇已經過的站點。每彈出一個油量，可達範圍增加該油量，直到燃油恢復為非負。
2. 證明延遲貪心
假設某個最優方案在需要補油時選擇較小的已經過油量 a，而堆中還有較大的 b。把這次選擇替換為 b，停止次數不變，當前位置之後的剩餘油量不減，因此後續路線仍可行。重複交換後，可得到總是選最大油量的同樣最優方案。
3. 統一扫描終點邊界
把終點 target 當作油量為 0 的虛擬站點，站點列表按位置排序後統一處理。目前位置從 0 開始，先計算相鄰位置差，再扣除差值。到達終點時若仍需補油，補油次數要計入答案；若沒有可用站點則回傳 -1。
4. 給出堆實作
Python 的 heapq 是最小堆，因此用負油量模擬最大堆。每個站點只入堆一次，每次真正補油才彈出並計數：
import heapq
def min_refuel_stops(target, start_fuel, stations):
fuel = start_fuel
previous = 0
max_heap = []
stops = 0
for position, station_fuel in [*stations, (target, 0)]:
fuel -= position - previous
while fuel < 0 and max_heap:
fuel += -heapq.heappop(max_heap)
stops += 1
if fuel < 0:
return -1
heapq.heappush(max_heap, -station_fuel)
previous = position
return stops5. 分析複雜度與測試邊界
設站點數為 n。每個油量最多入堆一次、出堆一次，時間複雜度為 O(n log n)，堆空間為 O(n)。測試應涵蓋初始油量足夠、第一站不可達、最後一站後仍需補油、油量為 0、多個同位置站點、剛好到達終點與目標不可達。
高品質示範回答
我會把終點作為油量為 0 的虛擬站點按序掃描。掃描時先扣除行駛距離，再把已經過站點的油量放入最大堆；當剩餘油量為負時，表示必須增加一次停止，就反覆取出歷史上最大的油量，直到能到達目前位置。若堆為空仍為負則回傳 -1。最大堆的正確性來自交換論證：在同一次被迫停止中，用較大的已經過油量替換較小油量不會增加停止次數，也不會減少後續可達範圍。每個站點最多入堆和出堆一次，因此複雜度為 O(n log n)，空間為 O(n)。
常見錯誤
- 到達站點就立即加油，把最少次數題誤寫成固定順序模擬。
- 只在站點之間檢查，不檢查最後一站到終點的距離。
- 混淆目前未使用油量與堆中可選油量。
- 使用最小堆取最小油量，破壞延遲貪心的最優性。
- 忘記站點只能在到達後加入堆，提前使用未來燃油。
- 只測試可達案例，沒有涵蓋空堆、零油量與溢位邊界。
追問及應對
為什麼不能每到一個站點就選最大油量？
因為目標是停止次數。提前取油可能增加停止次數，卻沒有改善最終可達性；延遲到燃油不足時再取，才能讓每次停止都解決真實的可達性限制。
如果每個站點可以部分加油怎麼辦？
題目目標與狀態會改變。若燃油價格或容量也參與最佳化，需要重新定義成本函數；目前證明依賴一次取走整站燃油且停止次數按站點計算。
為什麼同位置的多個站點不會破壞演算法？
它們的距離差為 0，可以按任意順序加入堆；只有後續需要補油時才選其中最大油量，結果與同時看到這些站點相同。
如何改成回傳實際停靠站點？
堆元素保存油量與站點索引。每次彈出時記錄索引；最後記錄的是延遲選擇的站點集合，按選擇時序或位置排序即可生成路線。