X

LEETCODE 1482. Minimum Number of Days to Make m Bouquets 解题思路分析

题目大意:

制作 m 束花所需的最少天数

给你一个整数数组 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]
显然,我们可以用不同的方式制作两束花。

示例 4:

输入:bloomDay = [1000000000,1000000000], m = 1, k = 1
输出:1000000000
解释:需要等 1000000000 天才能采到花来制作花束

示例 5:

输入:bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出:9

提示:

  • bloomDay.length == n
  • 1 <= n <= 10^5
  • 1 <= bloomDay[i] <= 10^9
  • 1 <= m <= 10^6
  • 1 <= k <= n

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1482

解题思路分析:

对于第D天时,能制作的花束个数,取决于所有值都要大于等于D(已开花)并且长度为k的不重合子数组个数。另外我们可以得知,随着D的增大,能制作的花束个数会增加,反之会减少。这是一个线性关系,因此,解题时会很容易想到使用二分查找的思路。

  1. 首先使用m乘以k判断制作m个花束一共需要多少多花,如果该数量大于花园总花朵数,返回-1。
  2. 循环一遍数组,找到最先开花(low)的时间与最晚开花的时间(high)
  3. 利用low和high作为二分查找的两个边界。(以下为标准二分思路)取中间值mid,并查看第mid天可以制作花束的数量。循环一遍数组,查看数值大于等于mid的连续子区间长度,该长度与k求商可得该子区间可制作花束的个数,并向后继续寻找连续大于等于mid的子区间。直到循环完数组中所有元素,可得当前一共可制作花束的个数。如果该个数大于等于m,将high变为mid-1。反之将low变为mid加一。重复上述过程直到low大于high为止
  4. low为最终答案。

实现代码:

public int minDays(int[] bloomDay, int m, int k) {
    // 花园中所有的花数量不够制作m个花束,返回-1
    if(m*k>bloomDay.length) return -1;
    // 花园中开花时间的最大值与最小值
    int low=bloomDay[0],high=bloomDay[0];
    for(int b : bloomDay){
        low=Math.min(low,b);
        high=Math.max(high,b);
    }
    // 二分查找
    while(low<=high){
        // 当前为第mid天时
        int mid=(low+high)/2;
        int count=0;
        int length=0;
        // 计算当前能制作的花束个数
        for(int b : bloomDay){
            if(b<=mid){
                length++;
            }else{
                count+=length/k;
                length=0;
            }
        }
        count+=length/k;
        // 如果个数大于等于需求m,减小high值
        if(count>=m) high=mid-1;
        else low=mid+1; // 反之增加low值
    }
    return low;
}

本题解法执行时间为16ms。

Runtime: 16 ms, faster than 94.31% of Java online submissions for Minimum Number of Days to Make m Bouquets.

Memory Usage: 48.1 MB, less than 100.00% of Java online submissions for Minimum Number of Days to Make m Bouquets.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1482-minimum-number-of-days-to-make-m-bouquets-解题思路分析/
Categories: leetcode
kwantong: