【Leetcode_Python】1642. Furthest Building You Can Reach

題目提供了一個陣列、磚塊和梯子的高度。其中陣列代表了建築的高度。

我們需要從第一個建築出發,我們需要使用磚塊(bricks) 或著梯子(ladders) 來幫助我們到達比目前所在建築高的建築,如果是比目前建築低的建築則不需要使用磚塊(bricks) 或著梯子(ladders)。

最後我們需要回傳我們能到達的最遠的建築。

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

  • If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
  • If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

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 <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= heights.length

Python 解答:

class Solution:
    def furthestBuilding(self, A, bricks, ladders):
        heap = []
        for i in range(len(A) - 1):
            d = A[i + 1] - A[i]
            if d > 0:
                heapq.heappush(heap, d)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
            if bricks < 0:
                return i
        return len(A) - 1
    

關於 heap

heapq.heappush(heapitem):把 item 放進 heap,並保持 heap 性質不變。

heapq.heappop(heap):從 heap 取出並回傳最小的元素,同時保持 heap 性質不變。如果 heap 是空的會產生 IndexError 錯誤。只存取最小元素但不取出可以使用 heap[0] 。

程式細節

for i in range(len(A) - 1):
    d = A[i + 1] - A[i]

首先我們來看 range的範圍,在 陣列A 的長度減去 1。這是因為我們需要用陣列中的後一個高度和目前的高度比較,如果範圍包括最後一個高度,他沒有後面的高度,這樣就會超出範圍。

if d > 0:
    heapq.heappush(heap, d)

如果後一個高度比目前的建築高的話,就把它放進 heap 中。

if len(heap) > ladders:
    bricks -= heapq.heappop(heap)

如果 heap 的長度大於 ladders,代表減去 ladders 也無法到達另一個 building,一定需要借助 bricks。因此,當 heap 的長度一大於 ladders,就用 bricks 減去 heap 中最小的高度。

if bricks < 0:
    return i

如果 bricks 小於 0,則回傳目前所在的位子。

之所以不需要 減去 ladders 是因為 len(heap) 的長度和 ladders 一樣,他們已經用掉了相應的梯子。

return len(A) - 1

如果順利跑到最後一個 building ,就回傳 A 的長度 -1,因為不包括第一個出發的建築,所以把 1 減去。

Leave a Comment

Your email address will not be published. Required fields are marked *