1482.Minimum Number of Days to Make m Bouquets¶
Tags: Medium Array Binary Search
Links: 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 == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
class Solution {
int n;
public:
int minDays(vector<int>& bloomDay, int m, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if ((long long)m * k > (long long)bloomDay.size()) return -1;
n = bloomDay.size();
int left = INT_MAX, right = INT_MIN;
for (int i = 0; i < n; ++i) {
left = min(left, bloomDay[i]);
right = max(right, bloomDay[i]);
}
while (left < right) {
int mid = left + ((right - left) >> 1);
if (!check(bloomDay, m, k, mid)) left = mid + 1;
else right = mid;
}
return left;
}
bool check(vector<int>& bloomDay, int m, int k, int target)
{
int cnt = 0, len = 0;
for (int i = 0; i < n; ++i) {
if (bloomDay[i] <= target) {
++len;
if (len == k) { ++cnt; len = 0; }
}
else len = 0;
}
return cnt >= m;
}
};
通过题目给出的第二个样例可知，我们首先应该检验如果所有的花都开了，是否可以满足要求。检验的时候注意到m \leq 10^6, k \leq n \leq 10^5，在计算m \times k的时候是可能溢出的，所以选择用long long。
如果所有花开的情况能够满足要求，那么结果的最大值就是序列bloomDay里的最大值，对应所有花开的情况；最好的情况是m = 1, k = 1，也就是只要有一朵花开就行，结果的最小值就是序列bloomDay里的最小值；其他情况肯定在这个范围内，分析到这里，基本上就是二分的板子了。
本题里很关键的是check函数的写法，不出意外所二分check基本都是只需要遍历一遍数组就可以完成检验。本题要求的是连续的k朵花，那么用len记录连续开花的个数，用target表示到目前等待的时间，所以只有bloomDay[i] <= target的才是花开的情况，当len == k的时候，计数器+1，len清零。如果cnt >= m意味着需要等待的时间一定不大于当前值，如果cnt < m，意味着需要等待的时间一定大于当前值，然后把思路转成二分代码即可。
最坏情况，数组最小数字为1，最大数字为10^9，数组长度为10^5，那么也只需要计算10^5 \times \log{10^9}，也不会超时。