You are given an integer array bloomDay, an integer m and an integer k.
You want 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.
你給予一個整數陣列 bloomDay、一個整數 m 和一個整數 k。 你想要製作 m 束的花束。要製作一束花束，你需要使用花園中 k 朵相鄰的花。 花園由 n 朵花組成，第 i 朵花將在 bloomDay[i] 開花，然後只能用於製作一束花朵。 回傳你需要等待得最少天數，以便能夠從花園中製作m 束花束。如果無法製作 m 束花束，則回傳 -1。
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 Output: 3 Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not 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.
Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2 Output: -1 Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 Output: 12 Explanation: We need 2 bouquets each should have 3 flowers. Here is the garden after the 7 and 12 days: After day 7: [x, x, x, x, _, x, x] We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent. After day 12: [x, x, x, x, x, x, x] It is obvious that we can make two bouquets in different ways.
Solution:
我們可以把題目給的 bloomDay[] 看作是一個會在第幾天開花的時間表，
而我們希望找到最小的天數來開出 m 束花且每束有 k 朵花相鄰。
我們先知道這個時間軸可以開出幾朵花 ( n = bloomDay.length)，
這裡可以做一個小判斷，如果 n < m * k 就回傳 -1，
因為開花表的總數量並不符合 m 束花乘上每束有 k 朵的數量。
再來我們可以先將這個時間表由小到大來排序，
這樣做可以幫助我們從最小可行天數來處理。
接著我們就可以用 Binary Search 來搜尋符合數量的答案(開花天數)，
你可以看成是我們把時間表切半從中間開始尋找，
如果在這一天能夠開出足夠的花束（≥ m），
代表答案可能還可以更小，於是縮小搜尋範圍到左半邊；
反之，如果花束數量不夠，就擴大搜尋範圍到右半邊。
最後如果有找到則回傳所需天數，如無則回傳 -1。
Code 1: BigO(n)
function minDays(bloomDay: number[], m: number, k: number): number {
const n: number = bloomDay.length;
if (n < m * k) return -1;
const days = [...bloomDay].sort((a, b) => a - b);
let min: number = -1;
let max: number = n;
while (max - min > 1) {
const mid: number = Math.floor((max + min) / 2);
const day: number = days[mid];
let bouquets: number = 0;
let count: number = 0;
for (let i = 0; i < n; i++) {
const bloomed: boolean = bloomDay[i] <= day;
count = bloomed ? count + 1 : 0;
if (count === k) {
bouquets++;
count = 0;
}
}
if (bouquets >= m) {
max = mid;
} else {
min = mid;
}
}
return max === n ? - 1: days[max];
};
FlowChart:
Example 1
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 days [ 1, 2, 3, 10, 10 ] index 0 1 2 3 4 mid 2 day 3 count 1 bouquets 1 count 0 count 1 bouquets 2 count 0 count 1 bouquets 3 count 0 🌸 第 3 天可以做出 3 束花 mid 0 day 1 count 1 bouquets 1 // 不符合 count 0 🌸 第 1 天可以做出 1 束花 mid 1 day 2 count 1 bouquets 1 count 0 count 1 bouquets 2 // 不符合 count 0 🌸 第 2 天可以做出 2 束花 bloomDay[1, 10, 3, 10, 2] index 0 1 2 3 4 第 1 天: ✅ ❌ ❌ ❌ ❌ 第 2 天: ✅ ❌ ❌ ❌ ✅ 第 3 天: ✅ ❌ ✅ ❌ ✅ return days[max]; // 3
Example 2
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2 n = 5, m * k = 3 * 2 = 6 n < m * k => return -1;
Example 3
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 days [7, 7, 7, 7, 7, 7, 12] index 0 1 2 3 4 5 6 mid 3 day 7 count 1 count 2 count 3 bouquets 1 count 0 count 1 count 1 count 2 🌸 第 7 天可以做出 1 束花 mid 5 day 7 count 1 count 2 count 3 bouquets 1 count 0 count 1 count 1 count 2 🌸 第 7 天可以做出 1 束花 mid 6 day 12 count 1 count 2 count 3 bouquets 1 count 0 count 1 count 2 count 3 bouquets 2 count 0 count 1 🌸 第 12 天可以做出 2 束花 bloomDay[7, 7, 7, 7, 12, 7, 7] index 0 1 2 3 4 5 6 第 7 天: ✅ ✅ ✅ ✅ ❌ ✅ ✅ 第 12天: ✅ ✅ ✅ ✅ ✅ ✅ ✅ return days[max]; // 12