[LeetCode] 1482. Minimum Number of Days to Make m Bouquets (JS)

6 個月前

內容目錄 隱藏

題目

你有一個整數陣列 bloomDay，其中 bloomDay[i] 表示第 i 朵花在第幾天會開花
你需要製作 m 束花
每束花需要 k 朵相鄰的花

目標是找出最少需要等待多少天才能製作出 m 束花。如果無法製作出 m 束花則返回 -1。

注意：要製作一束花需要”相鄰”的k朵花，不是相鄰就不能製作成花束。

Example1

輸入: bloomDay = [1,10,3,10,2], m = 3, k = 1

輸出: 3

你需要 3 束花，每束花需要 1 朵相鄰的花。
第 1 天： [x, _, _, _, _] （只能製作一束花）
第 2 天： [x, _, _, _, x] （可以製作兩束花）
第 3 天： [x, _, x, _, x] （可以製作三束花）因此答案是 3 天。

Example2

輸入: bloomDay = [1,10,3,10,2], m = 3, k = 2

輸出: -1

你需要 3 束花，每束花需要 2 朵相鄰的花，總共需要 6 朵花。
但花園中只有 5 朵花，無法製作出 3 束花，因此返回 -1。

Example3

輸入: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

輸出: 12

你需要 2 束花，每束花需要 3 朵相鄰的花。
第 7 天： [x, x, x, x, _, x, x] （可以製作一束花，無法製作第二束因為不相鄰）
第 12 天： [x, x, x, x, x, x, x] （可以製作兩束花）因此答案是 12 天。

解題思路

首先判斷花的數量是否足夠製作 m 束花（if (m*k > bloomDay.length) return -1）
使用二元搜索法，範圍為最早的開花天數至最晚開花的天數(left: 1, right: Math.max(bloomDay))，在每一步中檢查在當前天數下能否製作出 m 束花
1. 計算 left 和 right 的中間值mid，檢查在 mid 天時，是否能製作出 m 束每束包含 k 朵相鄰花的花束
2. 遍歷 bloomDay 陣列，計算在 mid 天時可以製作的花束數量
3. 新增一個變數 flowers 來紀錄當前連續開花的花朵數量
4. 當 flowers 的數量達到 k 時，表示可以製作一束花束，並將 bouquets 加1，然後重置 flowers
5. 如果 bloomDay[i] > mid，將 flowers 重置為0，因為這些花朵在 mid 天時還沒有開花，不能連續
6. 如果在 mid 天時可以製作出足夠的花束（bouquets >= m），則嘗試縮小搜索範圍，設置 right = mid - 1。
7. 否則，增大搜索範圍，設置 left = mid + 1。
當 left 超過 right 時結束搜索。此時，left 即為最少需要等待的天數。如果無法製作出足夠的花束，返回 -1。

完整程式碼

/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function(bloomDay, m, k) {
    // 如果總花朵數量少於所需的花朵數量，直接返回 -1
    if (bloomDay.length < m * k) return -1

    // 定義二元搜尋的範圍
    let left = 1
    let right = Math.max(...bloomDay)

    // 定義檢查函數，在指定天數內是否能製作出所需的花束
    const canMakeBouquets = (days) => {
        let bouquets = 0 // 可製作的花束數量
        let flowers = 0 // 當前連續開花的花朵數量

        for (let bloom of bloomDay) {
            if (bloom <= days) {
                flowers++
                if (flowers === k) {
                    bouquets++
                    flowers = 0
                }
            } else {
                flowers = 0
            }

            if (bouquets >= m) {
                return true
            }
        }

        return false
    }

   // 二元搜尋
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (canMakeBouquets(mid)) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return left <= Math.max(...bloomDay) ? left : -1
};