1482. Minimum Number of Days to Make m Bouquets

Leetcode link

解题思路

题目给了我们三个参数：

• bloomDay：Array，代表花园所有花各自开始盛开的天数
• m：Number，代表我们需要制作的花束数量
• k：Number，代表我们制作一束花束需要用到多少株花

此外，题目要求我们所有的花束都只能用（数组中）相邻的花来制作，且一枝花只能用来制作一个花束

这个题解题的思路是：我们需要一天天的比较现在盛开的花，看看哪一天符合制作所有花束的条件

因此，我们需要一个函数 canMakeBouquets 来帮我们判断某一天是否符合制作花束的条件了

此外，为了减少复杂度，我们可以使用二分法来减少计算的天数，二分法的范围从 1～bloomDay.length

详情请看代码：

Javascript

/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function(bloomDay, m, k) {
    if(m*k > bloomDay.length) {
        return -1;
    }

    const canMakeBouquets = (day) => {
        let bouquet = 0;
        let flowers = 0;
        for(const date of bloomDay) {
            if(date <= day) {
                if(++flowers === k) {
                    flowers = 0;
                    bouquet++;
                }
            } else {
                // not adjacent anymore
                flowers = 0;
            }
            if(bouquet >= m) {
                return true
            }
        }
        return false;
    }

    let low = 1, high = Math.max(...bloomDay);

    while(low < high) {
        let mid = Math.floor((low + high)/2);
        if(canMakeBouquets(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return low;
};