題目敘述
題目會給我們一個大樓陣列heights，裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目，和 ladders代表可用的伸縮爬梯數目。
假如下一棟比現在這棟大樓還矮，或者一樣高，則我們可以直接抵達下一棟。
假如下一棟比現在這棟大樓還高，我們可以選擇用疊磚塊補足高度的差值爬到下一棟，或者消耗一個伸縮爬梯爬到下一棟。
請問，最遠能抵達哪一棟大樓？
測試範例
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
約束條件
Constraints:
1 <= heights.length <= 10^5
輸入陣列的長度介於1~十萬之間。
1 <= heights[i] <= 10^6
每棟大樓的高度介於1~一百萬之間。
0 <= bricks <= 10^9
磚塊可用數目介於0~十億之間。
0 <= ladders <= heights.length
伸縮滑梯的數量介於0~輸入陣列heights長度之間。
演算法 Greedy + MinHeap
這題比較之後，可以發現功能比較強的是伸縮滑梯，因為用一次滑梯可以爬任意長度到達下一棟大樓；但是，用磚塊就必須一層一層慢慢疊上去才能爬到下一棟。
可以想到一個比較直覺的Greedy策略:
遇到比較高的大樓，先把高度差值記錄下來，並且儲存再minHeap最小堆裡面。
接著，假如梯子還有，就先消耗一個伸縮滑梯，用梯子爬過去。
假如梯子已經沒有了，就把之前看過差值最小那棟的取出來，把梯子拿回來，選擇用疊磚塊的方式爬過去之前看過差值最小那棟，並且扣掉對應的磚塊數量；接著在拿剛剛取回的梯子從現在這一棟爬到下一棟。
[這邊是整個演算法比較困難也是精華的一部分，可以在紙筆上跟著程式碼追蹤一遍]
假如最後梯子和磚塊都沒有了，那當下這棟大樓就是能抵達的最遠的那一棟大樓。
程式碼 Greedy + MinHeap
from heapq import heappush, heappop
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
# min heap to store building gaps
building_gap_heap = []
total_buildings = len(heights)
# scan each building pair's gap
for i in range( total_buildings-1 ):
cur_building_gap = heights[i+1] - heights[i]
if cur_building_gap > 0:
# next building is higher than current one, add to min heap
heappush(building_gap_heap, cur_building_gap)
if len(building_gap_heap) > ladders:
# the number of positive gaps is more than the number of ladders
# use bricks to fill those smaller gaps
gap_to_climb = heappop(building_gap_heap)
bricks -= gap_to_climb
if bricks < 0:
# we can not fill more gaps, because the bricks is run out
return i
# we can reach last building
return total_buildings-1
複雜度分析 Greedy + MinHeap
時間複雜度:
minHeap最大大小和梯子數量一樣多，每次動態調整需要O(log L)。
最多n回合，總共所需時間為O( n log L)
空間複雜度:
空間成本耗費在minHeap上，最大大小和梯子數量一樣多，最大所需空間為O(L)。
關鍵知識點
比較之後，知道梯子的功能比較強，先盡可能用梯子往右邊的高樓爬，如果梯子用完了，嘗試從前面已經看過高度差值最小的大樓取回梯子，用磚塊疊回去替代，假如最後磚塊也用完了，那當下這棟就是能抵達的最遠那一棟大樓。
Reference:
