LeetCode 筆記 - 1642. Furthest Building You Can Reach

Posted on

題目在此 1642. Furthest Building You Can Reach

給定一系列的建築高度、磚塊數量還有梯子數量，請給出最遠可以到達第幾棟建築

image 3

解題思維

我們先釐清一下題目，首先我們需要認知到磚塊可以抵達的高度有限，而梯子可以到達無限高度
所以梯子需要用在最重要的地方

但在掃描的過程中，我們無法知道哪裡才是最終該用梯子的地方
但是我們可以改變過去 :D

首先，我們一但遇到需要爬的地方一率先使用梯子，直到梯子使用完畢
這時我們需要維護一個 Priority queue 這通常會用 Heap 來實現
當我們使用了梯子，就把高度資訊放進我們的 Priority queue

這可以幫助我們在需要的時候給出過去爬過的最小高度

而當梯子用完時，我們就開始從 Priority queue 拿出過去最小的高度來替換成磚塊
這時我們又有一個梯子可以用了

持續這個過程直到磚塊用完

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        
        size = len(heights)
        min_heap = []
        
        for i in range(size - 1):
            if (climb := heights[i + 1] - heights[i]) <= 0:
                continue
                
            if climb > 0:
                heapq.heappush(min_heap, climb)
            
            # ladders are all in used, find the current shortest climb to use bricks instead!
            if len(min_heap) > ladders:
                # find the current shortest climb to use bricks
                bricks -= heapq.heappop(min_heap)

            if bricks < 0:
                return i
            
        return size - 1

🥹

相關文章