Problem Statement

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 Output: 3 Explanation: Let’s see what happened in the first three days. x means flower bloomed and _ means flower didn’t bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.

Ideas

这个问题是问最少需要等几天就可以摘到想要的花束，花束是需要m捧，每一捧要k只花，而且这k只花必须是连续的。咋眼一看，并没有什么特别好的办法，只能暴力解。注意到如果给定s天，我们是有办法判断等s天能不能摘到想要的花束。基于此，我们可以暴力试s=1:n。这样可行，时间复杂度为O(max(bloomDay)*n). n为len(bloomDay).

更进一步的优化为二分查找，我们不需要搜索所有的s=1:n天，每次判断可以把问题规模缩小为原来的一半。换一句说，如果发现等s天满足条件，那么s+1,…n肯定都可以满足条件，既然我们只关心最少需要多少天，那么s+1,…n就没有检查的意义了。

Solution

public int minDays(int[] bloomDay, int m, int k) {
    int left = 1;
    int right = 1;
    for (int bloom : bloomDay) {
        right = Math.max(right, bloom);
    }
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (isValid(bloomDay, m, k, mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    if (isValid(bloomDay, m, k, left)) {
        return left;
    }
    if (isValid(bloomDay, m, k, right)) {
        return right;
    }
    return -1;
}

private boolean isValid(int[] bloomDay, int m, int k, int day) {
    int bouquetCount = 0;
    int flowersCount = 0;
    for (int i = 0; i < bloomDay.length; i++) {
        if (bloomDay[i] <= day) {
            flowersCount++;
            if (flowersCount == k) {
                flowersCount = 0;
                bouquetCount++;
            }
        } else {
            flowersCount = 0;
        }
    }
    return bouquetCount >= m;
}

Analysis

时间复杂度为O(log(max(bloomDay))*n). n为len(bloomDay).