mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-13 23:40:35 +08:00
110 lines
3.6 KiB
Markdown
110 lines
3.6 KiB
Markdown
# [1482. Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)
|
||
|
||
## 题目
|
||
|
||
Given an integer array `bloomDay`, an integer `m` and an integer `k`.
|
||
|
||
We need to make `m` bouquets. To make a bouquet, you need to use `k` **adjacent flowers** from the garden.
|
||
|
||
The garden consists of `n` flowers, the `ith` flower will bloom in the `bloomDay[i]` and then can be used in **exactly one** bouquet.
|
||
|
||
Return *the minimum number of days* you need to wait to be able to make `m` bouquets from the garden. If it is impossible to make `m` bouquets return **-1**.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
|
||
Output: 3
|
||
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
|
||
We need 3 bouquets each should contain 1 flower.
|
||
After day 1: [x, _, _, _, _] // we can only make one bouquet.
|
||
After day 2: [x, _, _, _, x] // we can only make two bouquets.
|
||
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
|
||
Output: -1
|
||
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
|
||
```
|
||
|
||
**Example 3:**
|
||
|
||
```
|
||
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
|
||
Output: 12
|
||
Explanation: We need 2 bouquets each should have 3 flowers.
|
||
Here's the garden after the 7 and 12 days:
|
||
After day 7: [x, x, x, x, _, x, x]
|
||
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
|
||
After day 12: [x, x, x, x, x, x, x]
|
||
It is obvious that we can make two bouquets in different ways.
|
||
```
|
||
|
||
**Example 4:**
|
||
|
||
```
|
||
Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
|
||
Output: 1000000000
|
||
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.
|
||
```
|
||
|
||
**Example 5:**
|
||
|
||
```
|
||
Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
|
||
Output: 9
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `bloomDay.length == n`
|
||
- `1 <= n <= 10^5`
|
||
- `1 <= bloomDay[i] <= 10^9`
|
||
- `1 <= m <= 10^6`
|
||
- `1 <= k <= n`
|
||
|
||
## 题目大意
|
||
|
||
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
|
||
|
||
## 解题思路
|
||
|
||
- 本题是二分搜索提醒。题目解空间固定，答案区间一定在 [0, maxDay] 中。这是单调增且有序区间，所以可以在这个解空间内使用二分搜索。在区间 [0, maxDay] 中找到第一个能满足 m 束花的解。二分搜索判断是否为 true 的条件为：从左往右遍历数组，依次统计当前日期下，花是否开了，如果连续开花 k 朵，便为 1 束，数组遍历结束如果花束总数 ≥ k 即为答案。二分搜索会返回最小的下标，即对应满足题意的最少天数。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import "sort"
|
||
|
||
func minDays(bloomDay []int, m int, k int) int {
|
||
if m*k > len(bloomDay) {
|
||
return -1
|
||
}
|
||
maxDay := 0
|
||
for _, day := range bloomDay {
|
||
if day > maxDay {
|
||
maxDay = day
|
||
}
|
||
}
|
||
return sort.Search(maxDay, func(days int) bool {
|
||
flowers, bouquets := 0, 0
|
||
for _, d := range bloomDay {
|
||
if d > days {
|
||
flowers = 0
|
||
} else {
|
||
flowers++
|
||
if flowers == k {
|
||
bouquets++
|
||
flowers = 0
|
||
}
|
||
}
|
||
}
|
||
return bouquets >= m
|
||
})
|
||
}
|
||
``` |