ETH官方钱包

前往
大廳
主題

LeetCode - 1482. Minimum Number of Days to Make m Bouquets 解題心得

Not In My Back Yard | 2022-12-25 12:00:05 | 巴幣 1100 | 人氣 267

題目連結:


題目意譯:
你被給定一整數陣列 bloomDay,以及一個整數 m 和一整數 k。

你想要製作 m 個花束。為了製作一個花束,你需要使用花園中 k 朵相鄰的花朵。

花園由 n 朵花所組成,第 i 朵花將於第 bloomDay[i] 天開花並且只能使用於恰好一個花束中。

回傳你從花園製作 m 個花束你最少所需等待的天數。如果不可能做出 m 個花束,則回傳 -1。

限制:
bloomDay.length == n
1 ≦ n ≦ 10 ^ 5
1 ≦ bloomDay[i] ≦ 10 ^ 9
1 ≦ m ≦ 10 ^ 6
1 ≦ k ≦ n



範例測資:
範例 1:
輸入: bloomDay = [1,10,3,10,2], m = 3, k = 1
輸出: 3
解釋: 讓我們來看看前三天發生了什麼。在花園中,x 代表著花開了,而 _ 代表著花尚未開。
我們需要 3 個花束,而每一個應包含 1 朵花。
在第 1 天後: [x, _, _, _, _]   // 我們只能製作一個花束。
在第 2 天後: [x, _, _, _, x]   // 我們只能製作兩個花束。
在第 3 天後: [x, _, x, _, x]   // 我們只能製作三個花束。答案是 3。

範例 2:
輸入: bloomDay = [1,10,3,10,2], m = 3, k = 2
輸出: -1
解釋: 我們需要 3 個花束,而每一個應包含 2 朵花。這代表著我們需要 6 朵花。我們只有 5 朵花,所以不可能製作出所需的花束數量,所以回傳 -1。

範例 3:
輸入: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
輸出: 12
解釋: 我們需要 2 個花束,而每一個應包含 3 朵花。
以下是經過 7 天和 12 天後的花園:
在第 7 天後: [x, x, x, x, _, x, x]
我們可以從前三朵已經開花的花兒們來製作出一個花束。我們沒辦法藉由後三朵已經開的花來做出另一個花束,因為它們並不是相鄰的。
在第 12 天後: [x, x, x, x, x, x, x]
很明顯地,我們可以用不同的方式來製作出兩個花束。


解題思維:
這題類似,對答案進行二分搜尋法(Binary Search)即可。



我們可以猜一個天數 D。接著我們可以試試看這個 D 值可不可能:
此時我們可以按照範例把已經開花的標記成「x」(雖然實際上不需要,只是比較好說明),然後數連續的 k 個 x(假設有 C 個這樣子的區間)。

如果 C < m,代表天數猜太小,要猜大一點;反之,可以試著猜小一點的天數。

最後便可以找到可行且最小的天數值,即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作