题目如下:
给你一个整数数组 bloomDay
,以及两个整数 m
和 k
。
现需要制作 m
束花。制作花束时,需要使用花园中 相邻的 k
朵花 。
花园中有 n
朵花,第 i
朵花会在 bloomDay[i]
时盛开,恰好 可以用于 一束 花中。
请你返回从花园中摘 m
束花需要等待的最少的天数。如果不能摘到 m
束花则返回 -1 。
做题思路:
首先如果总的花数量小于所需要的花数量直接返回-1;否则无论如何都会有满足的天数。
对于辅助函数的实现,可以遍历数组 ,计算其中的长度为k, 且最大元素不超过设定的值,不重合的连续子数组的数量,如果符合要求的不重合的连续子数组的数量大于或等于 m 则返回 true,否则返回 false。
我们可以使用二分查找,这样就可以避免设定的值太小或者太大,太小的话辅助函数一直返回false,效率很低,太大的话无论如何都是true,导致返回的天数会非常大。
这是实现功能的主要函数,其中复用了辅助函数进行判断
int minDays(vector<int>& bloomDay, int m, int k) {
if(m > bloomDay.size() / k)
{
return -1;
}
int low=INT_MAX,high=0;
int num=bloomDay.size();
for(int i=0;i<num;i++)
{
low=min(bloomDay[i],low);
high=max(bloomDay[i],high);
}
while(low<high)
{
int days=(high-low)/2+low;
if(truee(bloomDay,days,m,k))
{
high=days;
}
else
{
low=days+1;
}
}
return low;
}
辅助函数中主要是对数组中连续的花朵天数进行判断,如果符合要求则返回true。
bool truee(vector<int>& bloomDay,int days,int m,int k)
{
int num=0;
int sum=0;
int sizes=bloomDay.size();
for(int i=0;i<sizes&&num<m;i++)
{
if(bloomDay[i]<=days)
{
sum++;
if(sum==k)
{
num++;
sum=0;
}
}
else{
sum=0;
}
}
return num>=m;
}