今天 (2/17) 的 Daily 是 Medium 題： Leetcode 1642. Furthest Building You Can Reach

目錄

題目分析

題目

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.

給你一個整數數組heights ，表示建築物的高度。另一些磚塊bricks 和梯子ladders 。

你從建築物0 開始旅程，不斷向後面的建築物移動，期間可能會用到磚塊或梯子。

當從建築物i 移動到建築物i+1（下標從0 開始）：

如果目前建築物的高度大於或等於下一棟建築物的高度，則不需要梯子或磚塊如果當前建築的高度小於下一個建築的高度，您可以使用一架梯子或(h[i+1] - h[i]) 個磚塊如果以最佳方式使用給定的梯子和磚塊，返回你可以到達的最遠建築物的下標（下標從0 開始）。

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 <= heights[i] <= 10^6
0 <= bricks <= 10^9
0 <= ladders <= heights.length

分析

大致歸納題目：

heights代表每棟建築物的高度，從一棟建築物到下一棟建築物時：

  1. 假如下一棟建築物等高或較矮，則可以直接移動過去
  2. 假如下一棟建築物較高，則從下列二者擇一：
    1. 花費數量 = 高度差的brick
    2. 花費1個ladder

求能到達的最遠建築的index。

這乍看之下是一個DP問題，有一點像0/1背包問題(在每一個較高建築前面決定要用梯子或者磚塊來前進)

解題思路

方案一、動態規劃(0/1背包問題)：

從動態規劃的角度來看，子問題相當顯而易見。

當我位在第i棟房，剩餘b塊磚與l個梯子，則最遠可以前進到哪棟房

以solve(i, b, l)代表這個子問題的答案。

對於一般性的子問題，首先計算這棟房與下棟房的高度差gap

gap = height[i+1] - height[i]

  1. 當gap<=0，代表不需要消耗任何道具即可前進，即：

    solve(i, b, l) = solve(i+1, b, l)

  2. 當gap>0，要選擇消耗磚或者梯子來前進，即

    1. 磚變為b-gap
    2. 梯子變為l-1

    求其中較好的結果即為最佳局部解：

    solve(i, b, l) = max( solve(i+1, b-gap, l) , solve(i+1, b, l-1) )

並且，考慮邊界條件(base case)，也就是何種狀態將無法繼續前進至i+1：

  1. 當i = len(heights) -1，也就是走到底了，此時局部解solve(i, b, l) = i
  2. 當b<gap且i=0，也就是磚和梯子都不夠了，就無法繼續前進，此時局部解solve(i, b, l) = i

原本所求問題則為 solve(0, bricks, ladders)，遞迴求解即可。

範例程式碼 (Python 3)

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        last = len(heights)-1
        @cache
        def solve(i, b, l):
            if b<0 or l<0: return i-1
            if i==last: return i
            gap = heights[i+1]-heights[i]
            if gap<=0: return solve(i+1,b,l)
            return max(solve(i+1, b-gap, l), solve(i+1, b, l-1))
        return solve(0, bricks, ladders)

複雜度分析

因為需要同時記錄i、b、l三個參數，所以如果buttom-up DP的作法，需要很大的空間，S = O(n x m x k)，其中n、m、k分別為i、b、l的範圍。以本題測資來說，會吃MLE。即使以top-down DP + memoization(上例的cache函式)來處理，只記錄需要計算的子問題答案，但由於本題的bricks <= 10^9範圍很大，所以仍然會吃MLE。

alt text

另外，由於時間複雜度亦為T = O(n x m x k)，所以應該也是要吃TLE。

有沒有更節省時間和空間的作法呢？那就往貪心的方向試試看吧！

方案二、貪心算法

本題和 0/1 背包問題其實有一個很大的區別：

在0/1背包問題中，小偷對所有看見的物品都能選擇拿或不拿，然而在本題我們若要前進，卻又不想消耗磚塊(相當於背包問題的背包容量)，就必須使用梯子。而這個梯子也是有數量限制的。

換言之，並不是「拿與不拿」，而是「不拿哪些」(在哪些房子使用梯子)。

貪心算法

簡化題目：假設只有1把梯子。

貪心的策略很簡單：

只要一直前進並總是使用磚塊，並且當磚塊不夠時，把過程中最大的gap改成使用梯子，就必定能前進到最遠的距離。

只要證明其正確性：

假設我們在gap最大的a房子使用了梯子，因此節省了gap[a]的磚塊。

要比這個答案更佳，不使用任何梯子很顯然行不通(因為要多花費gap[a]的磚塊，磚塊會更早不夠用)。如果改將梯子用在b房子，因此節省了gap[b]的磚塊，但因為a是途中gap最大的那間房子，因此gap[a]>gap[b]，一來一往磚塊的消耗還是更多了。

換言之，一開始貪心策略找到的答案便是最佳答案。

接著把貪心策略推廣到N把梯子吧。

策略也很類似：只要一直前進並總是使用磚塊，並且當磚塊不夠時，把過程中最大的N個gap改成使用梯子。

不過，貪心策略還有一個小問題：

我們將1(或N)個gap換成了梯子，因此節省了一些磚塊。假如使用這些省下來磚塊前進的過程，又遇到了更大的gap呢？

根據貪心策略，我們應該總是把梯子用在最大的gap上。換言之，在一邊前進的過程，需要一邊記錄並且更新「目前為止最大的N個gap」(使用梯子)，並且計算不使用梯子的剩下來gap，確認磚塊是否夠用。

當磚塊終於不夠時，這次就是真正的答案了。

範例程式碼 (Python 3)

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        maxN = []
        for i in range(len(heights)-1):
            gap = heights[i+1]-heights[i]
            if gap<=0: continue
            maxN.append(gap)
            if len(maxN) > ladders:
                maxN.sort(reverse=True)
                bricks -= maxN.pop()
                if bricks<0: return i
        else: 
            return len(heights)-1

維護maxN這個list，當作我們要使用梯子的gap。當陣列長度超過梯子的數量時，便對其進行排序，以取出其中最小的gap，改成消耗磚塊。不斷迭代直到磚塊的數量不夠為止。

複雜度分析

空間複雜度：因為只需要維護一個陣列，空間複雜度降為S = O(k)

時間複雜度：T = O(n x k log(k) )

對0<=i<n迭代，並且在每次迴圈中對長度為k = ladders的陣列進行排序

時間複雜度為T = O(n x k log(k) )

雖然解決了MLE，且時間上比DP稍微優化(從m降為log k)，但這樣仍然是吃TLE的。

alt text

究其原因，我們在每次迭代中，為了取出當前最小的gap，對其使用了排序，造成每次 T = O(k log k)的時間消耗。

如果只是為了取出陣列中的最小值，則有一個資料型態能以更短的時間完成：那就是「優先佇列」(priority queue)

方案三 Greedy + priority queue

優先佇列 priority queue

優先佇列是一種特殊的資料結構，可以總是取出其中最小的元素。要實作一個優先佇列，可以使用堆疊(heap)

heap是一種特殊的完全二元樹，其所有的親節點都大於其子節點，又稱為最小堆疊(min heap)，與之相反的則是最大堆疊(max heap)。

在Python上要實作min heap，除了使用tree或者list並自己實作插入/取出的演算法之外，也可以使用基本函式庫裡面的heapq模組。

優先佇列(最小堆疊)相關的時間複雜度：

  • 若其長度為L，則放入新元素(並維持堆疊)與取出最小元素的時間複雜度都是T = O(log L)

  • 將一個普通陣列修改為堆疊(heapify)，需要T=O(L)

  • 利用堆疊將一個普通陣列排序(heapsort)，需要T = O(L log L)

本文不討論min heap的實作，直接使用heapq模組來解題。

heapq模組

原始碼與文件

import heapq

# 初始化
h = []                      # 建立一個空的 heap，或者
h = heapq.heapify(list)     # 將一個 list 初始化為 heap

# 操作 ( h 必須先初始化為 heap )
h[0]                        # 讀取最小元素(不取出)
heapq.heappop(h)            # 取出並回傳最小元素
heapq.heappush(h, item)     # 在 h 中放入 item
heapq.heappushpop(h, item)  # 在 h 中放入 item 之後取出最小元素
heapq.heapreplace(h, item)  # 取出最小元素之後將 item 放入 h 中

本題會用到heappush、heappop以及heappushpop的操作。

範例程式碼 (Python 3)

把方案二的程式碼中，進出陣列以及排序的部分替換成heap操作就完成了。

import heapq
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        maxN = []
        for i in range(len(heights)-1):
            gap = heights[i+1]-heights[i]
            if gap<0: continue
            if len(maxN)<ladders: 
                heapq.heappush(maxN, gap)
            else:
                bricks -= heapq.heappushpop(maxN, gap)
                if bricks<0: return i
        else: 
            return len(heights)-1

複雜度分析

遍歷i<n並且維護一個大小為k=ladders的heap

時間複雜度為：T = O(n log k)

空間複雜度為：S = O(k)

結語

其實筆者一開始就考慮 Greedy + Heap 的作法，不過在寫文的時候逛別人的solution才發覺這是個似是而非的(假)0/1背包問題，還好沒中陷阱啊XD

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！