MediumRating 1536
1642. Furthest Building You Can Reach
arraygreedyheap-priority-queue
解題說明
Furthest Building You Can Reach
題目描述：給定建築高度陣列 heights、磚頭數 bricks 和梯子數 ladders。從第 0 棟出發，往右移動時若下一棟比當前高，需消耗高度差的磚頭或使用一個梯子（梯子可跨越任意高度差）。回傳能到達的最遠建築索引。
解題思路：貪心策略：梯子應留給高度差最大的躍升，磚頭用於較小的高度差。
使用最小堆（min-heap）追蹤「已使用梯子」的高度差。每遇到一個正高度差 d，先假設用梯子跨越（將 d 加入堆）。若堆的大小超過 ladders，代表梯子不夠，需將堆中最小的高度差改用磚頭來彌補（從堆頂取出並從 bricks 扣除）。若磚頭不足（bricks < 0），則無法繼續，回傳當前索引。
這種「反悔貪心」的思路：先貪心地對每個高度差使用梯子，一旦梯子超額就把歷史中最划算（高度差最小）的梯子用途替換成磚頭。
C++ 解法
複雜度分析
時間複雜度：O(n log L) — n 為建築數，L 為梯子數。每個正高度差最多入堆一次、出堆一次，堆大小不超過 L+1，每次操作為 O(log L)。
空間複雜度：O(L) — 最小堆最多同時存放 L 個元素（梯子數），不隨建築數量增長。
虛擬碼
1. Initialize min-heap H (empty), bricks and ladders as given.
2. For i from 0 to n-2:
a. Compute diff = heights[i+1] - heights[i].
b. If diff <= 0: continue (no cost).
c. Push diff into H (tentatively use a ladder).
d. If size(H) > ladders:
- bricks -= H.top(); pop H.top().
- If bricks < 0: return i.
3. Return n - 1 (reached the last building).其他解法
方法一：二分搜尋 + 貪心
對答案（能到達的最遠索引）二分搜尋，對每個候選答案 mid，貪心地將 ladders 個最大高度差用梯子、其餘用磚頭，確認磚頭是否足夠。時間複雜度 O(n log n)，空間 O(n)，思路也正確但常數較大。
方法二：最大堆（梯子留給最大差） 另一種貪心：對每個高度差先用磚頭，同時維護最大堆記錄已用磚頭的高度差。若磚頭不足，從堆中取出最大值（改用梯子）以節省磚頭。邏輯對稱但代碼略微不同，時空複雜度相同。
方法三：暴力模擬 枚舉終點，對每種梯子分配方案檢驗可行性。時間複雜度指數級，僅適用於極小規模測試。
延伸思考
- 若梯子的承載能力有上限（例如梯子最高只能跨越高度差 100），如何修改貪心策略？
- 若磚頭和梯子可以部分使用（例如一個梯子可拆為兩個半梯子各用一次），問題會如何改變？
- 本題的「反悔貪心 + 最小堆」模式在哪些其他場景中常見？與任務排程問題有何相似之處？