模擬: 最遠可以抵達的大樓 Furthest Building You Can Reach_Leetcode #142

Chris Czermak on Unsplash

題目敘述

題目會給我們一個大樓陣列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:

[1] Furthest Building You Can Reach - LeetCode