給你一個整數數組 bloomDay,以及兩個整數 m 和 k 。
現需要制作 m 束花。制作花束時,需要使用花園中 相鄰的 k 朵花 。
花園中有 n 朵花,第 i 朵花會在 bloomDay[i] 時盛開,恰好 可以用于 一束 花中。
請你返回從花園中摘 m 束花需要等待的最少的天數。如果不能摘到 m 束花則返回 -1 。
示例 1:
輸入:bloomDay = [1,10,3,10,2], m = 3, k = 1
輸出:3
解釋:讓我們一起觀察這三天的花開過程,x 表示花開,而 _ 表示花還未開。
現在需要制作 3 束花,每束只需要 1 朵。
1 天后:[x, _, _, _, _] // 只能制作 1 束花
2 天后:[x, _, _, _, x] // 只能制作 2 束花
3 天后:[x, _, x, _, x] // 可以制作 3 束花,答案為 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]
可以用前 3 朵盛開的花制作第一束花。但不能使用后 3 朵盛開的花,因為它們不相鄰。
12 天后:[x, x, x, x, x, x, x]
顯然,我們可以用不同的方式制作兩束花。
解題思路
使用二分查找,查找出滿足情況的最小日期
檢查是否滿足條件:遍歷數組,如果開花日期是在限制日期前就作為有效的花朵,連續的k朵花,可作為一個有效花束,檢查可以生產花束的個數是否多于m
代碼
func minDays(bloomDay []int, m int, k int) int {n:=len(bloomDay)if n<m*k{return -1}max:=-1for _, day := range bloomDay {if day>max{max=day}}return sort.Search(max, func(days int) bool {cnt ,f:=0,0for i := 0; i < n; i++ {if bloomDay[i]>days{cnt=0}else{cnt++if cnt==k{f++cnt=0}}}return f>=m})
}