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

标签：数组、二分查找
难度：中等

题目大意 #

给定一个整数数组 bloomDay，以及两个整数 m 和 k。bloomDay 代表花朵盛开的时间，bloomDay[i] 表示第 i 朵花的盛开时间。盛开后就可以用于一束花中。

现在需要制作 m 束花。制作花束时，需要使用花园中相邻的 k 朵花。

要求：返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1。

解题思路 #

这道题跟「 0875. 爱吃香蕉的珂珂」、「 1011. 在 D 天内送达包裹的能力」有点相似。

根据题目可知：

制作花束最少使用时间跟花朵开花最短时间有关系，即 min(bloomDay)。
制作花束最多使用时间跟花朵开花最长时间有关系，即 max(bloomDay)。
则制作花束所需要的天数就变成了一个区间 [min(bloomDay), max(bloomDay)]。

那么，我们就可以根据这个区间，利用二分查找算法找到一个符合题意的最少天数。而判断某个天数下能否摘到 m 束花则可以写个方法判断。具体步骤如下：

遍历数组 bloomDay。
如果 bloomDay[i] 小于等于天数 days。就将花朵数量 + 1。
- 当能摘的花朵数等于 k 时，能摘的花束数目 + 1，花朵数量置为 0。
如果 bloomDay[i] 大于天数 days。就将花朵数置为 0。
最后判断能摘的花束数目是否大于等于 m。

整个算法的步骤如下：

如果 m * k 大于 len(bloomDay)，说明无法满足要求，直接返回 -1。
使用两个指针 left、right。令 left 指向 min(bloomDay)，right 指向 max(bloomDay)。代表待查找区间为 [left, right]。
取两个节点中心位置 mid，判断是否能在 mid 天制作 m 束花。
- 如果不能，则将区间 [left, mid] 排除掉，继续在区间 [mid + 1, right] 中查找。
- 如果能，说明天数还可以继续减少，则继续在区间 [left, mid] 中查找。
当 left == right 时跳出循环，返回 left。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def canMake(self, bloomDay, days, m, k):
        count = 0
        flower = 0
        for i in range(len(bloomDay)):
            if bloomDay[i] <= days:
                flower += 1
                if flower == k:
                    count += 1
                    flower = 0
            else:
                flower = 0
        return count >= m

    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m > len(bloomDay) / k:
            return -1

        left, right = min(bloomDay), max(bloomDay)

        while left < right:
            mid = left + (right - left) // 2
            if not self.canMake(bloomDay, mid, m, k):
                left = mid + 1
            else:
                right = mid

        return left

参考资料 #

【题解】【赤小豆】为什么是二分法，思路及模板 python - 制作 m 束花所需的最少天数 - 力扣（LeetCode）