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

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

題目

  • 你有一個整數陣列 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 天。

解題思路

  1. 首先判斷花的數量是否足夠製作 m 束花(if (m*k > bloomDay.length) return -1
  2. 使用二元搜索法,範圍為最早的開花天數至最晚開花的天數(left: 1, right: Math.max(bloomDay)),在每一步中檢查在當前天數下能否製作出 m 束花
    1. 計算 leftright 的中間值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
  3. 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
};
guest

0 評論
內聯回饋
查看全部評論