二分查找题目：制作 m 束花所需的最少天数

题目

标题和出处

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

出处：1482. 制作 m 束花所需的最少天数

难度

5 级

题目描述

要求

给定一个整数数组 $\text{bloomDay}$，以及两个整数 $\text{m}$ 和 $\text{k}$。

现需要制作 $\text{m}$ 束花。制作花束时，需要使用花园中相邻的 $\text{k}$ 朵花。

花园中有 $\text{n}$ 朵花，第 $\text{i}$ 朵花会在第 $\text{bloomDay[i]}$ 天盛开，恰好可以用于一束花中。

返回从花园中制作 $\text{m}$ 束花需要等待的最少的天数。如果不能制作 $\text{m}$ 束花则返回 $\text{-1}$。

示例

示例 1：

输入：$\text{bloomDay = [1,10,3,10,2], m = 3, k = 1}$
输出：$\text{3}$
解释：以下是前三天的花开过程，$\text{x}$ 表示花开，而 $\text{\_}$ 表示花还未开。
现在需要制作 $\text{3}$ 束花，每束需要 $\text{1}$ 朵花。
$\text{1}$ 天后：$\text{[x, \_, \_, \_, \_]}$ // 只能制作 $\text{1}$ 束花。
$\text{2}$ 天后：$\text{[x, \_, \_, \_, x]}$ // 只能制作 $\text{2}$ 束花。
$\text{3}$ 天后：$\text{[x, \_, x, \_, x]}$ // 可以制作 $\text{3}$ 束花，答案为 $\text{3}$。

示例 2：

输入：$\text{bloomDay = [1,10,3,10,2], m = 3, k = 2}$
输出：$\text{-1}$
解释：要制作 $\text{3}$ 束花，每束需要 $\text{2}$ 朵花，因此一共需要 $\text{6}$ 朵花。而花园中只有 $\text{5}$ 朵花，无法满足制作要求，返回 $\text{-1}$。

示例 3：

输入：$\text{bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3}$
输出：$\text{12}$
解释：要制作 $\text{2}$ 束花，每束需要 $\text{3}$ 朵花。
花园在 $\text{7}$ 天后和 $\text{12}$ 天后的情况如下：
$\text{7}$ 天后：$\text{[x, x, x, x, \_, x, x]}$
可以用前 $\text{3}$ 朵盛开的花制作第一束花。但不能使用后 $\text{3}$ 朵盛开的花，因为它们不相邻。
$\text{12}$ 天后：$\text{[x, x, x, x, x, x, x]}$
显然，我们可以用不同的方式制作两束花。

数据范围

• $\text{bloomDay.length}=\text{n}$
• $\text{1}\le \text{n}\le {\text{10}}^{\text{5}}$
• $\text{1}\le \text{bloomDay[i]}\le {\text{10}}^{\text{9}}$
• $\text{1}\le \text{m}\le {\text{10}}^{\text{6}}$
• $\text{1}\le \text{k}\le \text{n}$

解法

思路和算法

为了制作 $m$ 束花，每束需要 $k$ 朵花，共需要 $m\times k$ 朵花。花园中有 $n$ 朵花，如果 $m\times k>n$，则即使将全部 $n$ 朵花都用于制作花束也无法满足制作要求，因此返回 $-1$。

当 $m\times k\le n$ 时，制作全部花束需要的花不超过 $n$ 朵，因此当所有花都盛开时，一定可以制作全部花束。

如果等待天数大于等于最少天数，则可以制作全部花束；如果等待天数小于最少天数，则不能制作全部花束。因此，这道题是二分查找判定问题，需要找到最少天数。

用 $\text{low}$ 和 $\text{high}$ 分别表示二分查找的下界和上界。由于 $m$ 和 $k$ 都至少是 $1$，且每朵花盛开的天数都至少是 $1$ 天，因此 $\text{low}$ 的初始值等于 $1$；由于当所有花都盛开时一定可以制作全部花束，因此 $\text{high}$ 的初始值等于 $\text{bloomDay}$ 中的最大值。

当等待天数是 $\text{days}$ 时，$\text{bloomDay}$ 中的小于等于 $\text{days}$ 的元素对应的花已经盛开，$\text{bloomDay}$ 中的大于 $\text{days}$ 的元素对应的花尚未盛开。由此可以得到每朵花是否盛开，并根据连续盛开的花朵数计算可以制作多少束花。

每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，将 $\text{mid}$ 作为等待天数，判断是否可以制作全部花束，执行如下操作。

• 如果等待天数是 $\text{mid}$ 时可以制作全部花束，则最少天数小于等于 $\text{mid}$，因此在 $[\text{low},\text{mid}]$ 中继续查找。

• 如果等待天数是 $\text{mid}$ 时不能制作全部花束，则最少天数大于 $\text{mid}$，因此在 $[\text{mid}+1,\text{high}]$ 中继续查找。

当 $\text{low}=\text{high}$ 时，查找结束，此时 $\text{low}$ 即为最少天数。

代码

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) {
            return -1;
        }
        int low = Arrays.stream(bloomDay).min().getAsInt(), high = Arrays.stream(bloomDay).max().getAsInt();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canMakeMBouquets(bloomDay, m, k, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public boolean canMakeMBouquets(int[] bloomDay, int m, int k, int days) {
        int bouquets = 0;
        int consecutive = 0;
        int n = bloomDay.length;
        for (int i = 0; i < n; i++) {
            if (bloomDay[i] <= days) {
                consecutive++;
                if (consecutive % k == 0) {
                    bouquets++;
                    if (bouquets == m) {
                        return true;
                    }
                }
            } else {
                consecutive = 0;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：$O(n\log m)$，其中 $n$ 是数组 $\text{bloomDay}$ 的长度，$m$ 是数组 $\text{bloomDay}$ 中的最大值。需要执行 $O(\log m)$ 次二分查找，每次二分查找需要 $O(n)$ 的时间遍历数组 $\text{bloomDay}$ 判断是否可以制作全部花束，时间复杂度是 $O(n\log m)$。

• 空间复杂度：$O(1)$。