🔗 🟡 1482. Minimum Number of Days to Make m Bouquets 1946

tags: `Week Contest 193` `二分搜尋(Binary Search)`

題意

給定一個長度為 $n$ 的整數陣列 $\text{bloomDay}$ ，一個整數 $m$ 和一個整數 $k$ 。

花園中有 $n$ 朵花，第 $i$ 朵花將在 $\text{bloomDay}[i]$ 開花。

現在需要製作 $m$ 個花束，製作一個花束時，需要使用花園中相鄰的 $k$ 朵花。

返回從花園中製作 $m$ 個花束需要等待的最少天數。如果無法製作 $m$ 個花束則返回 $-1$ 。

約束條件

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

思路：二分搜尋(Binary Search)

首先確定思路，顯然要直接計算出最少需要等待的天數是很困難的，但對於給定的天數 $d$ ，我們可以確定是否可以在 $d$ 天內製作 $m$ 個花束，因此可以使用二分搜尋(Binary Search) 來找到最少需要等待的天數。

定義一個函數 check(d) 來檢查在待定天數 $d$ 內是否能製作出 $m$ 個花束，每束花需要使用相鄰的 $k$ 朵花。

使用 $res$ 來記錄製作的花束數量， $cur$ 來記錄相鄰花的數量。
遍歷 $\text{bloomDay}$ $bloomDay$ 陣列中的每個元素 $\text{bloom}$ $bloom$
- 如果 $\text{bloom} \leq d$ ，代表這朵花可以被使用，則 $cur$ 加一。如果 $cur = k$ ，代表有 $k$ 朵相鄰花可以製作花束，則 $res$ 加一， $cur$ 重置為 $0$ 。
- 如果 $\text{bloomDay}[i] > d$ ，則代表這朵花在 $d$ 天時還沒開花，由於使用的花必須是相鄰的，因此需要把相鄰花的數量重置為 $0$ 。
最後返回 $res \geq m$ ，即是否可以製作 $m$ 個花束。

這裡使用左閉右閉區間進行二分搜尋，令 $left = \min(\text{bloomDay})$ ， $right = \max(\text{bloomDay})$ ，在 $[left, right]$ 的範圍內進行二分搜尋，不斷調整左右範圍直到找到最小天數為止。

根據定義的 check 函數，區間的左側為 $\text{False}$ ，而右側為 $\text{True}$ 。
如果 $\text{check}(mid) = \text{True}$ ，則將右範圍縮小到 $[left, mid-1]$ 。
如果 $\text{check}(mid) = \text{False}$ ，則將左範圍擴大到 $[mid+1, right]$ 。
當區間為空，即 $left > right$ 時，終止搜尋。

最終返回 $left$ ，即第一個 check 函數返回 $\text{False}$ 的天數，如果 $left > \max(\text{bloomDay})$ ，則表示無法製作 $m$ 個花束，返回 $-1$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n \log M)$ 。其中 $n = |\text{bloomDay}|$ ， $M = \max(\text{bloomDay})$ ，我們需要進行 $\log M$ 次二分搜尋。每次搜尋需要遍歷 $n$ 個元素來檢查是否可以製作 $m$ 個花束。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        # check if we can make m bouquets with k flowers in d days
        def check(d: int):
            res = cur = 0 # res: number of bouquets, cur: number of adjacent flowers
            for bloom in bloomDay:
                if bloom <= d:
                    cur += 1
                    if cur == k:
                        res += 1
                        cur = 0
                else: # not adjacent
                    cur = 0
            return res >= m
        
        left, right = min(bloomDay), max(bloomDay)
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left if left <= max(bloomDay) else -1

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        
        // check if we can make m bouquets with k flowers in d days
        auto check = [&](int d) {
            int res = 0, cur = 0;
            for (int bloom : bloomDay) {
                if (bloom <= d) {
                    cur++;
                    if (cur == k) {
                        res++;
                        cur = 0;
                    }
                } else {  // not adjacent
                    cur = 0;
                }
            }
            return res >= m;
        };

        int mx = INT_MIN, mn = INT_MAX;
        for (int bloom : bloomDay) {
            mx = max(mx, bloom);
            mn = min(mn, bloom);
        }
        int left = mn, right = mx;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left <= mx ? left : -1;
    }
};