Сложность: medium
Вам дан массив целых чисел bloomDay, целое число m и целое число k.
Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.
Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -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.
👨💻 Алгоритм:
1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.
2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.
3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.
😎 Решение:
class Solution:
def getNumOfBouquets(self, bloomDay, mid, k):
numOfBouquets = 0
count = 0
for day in bloomDay:
if day <= mid:
count += 1
else:
count = 0
if count == k:
numOfBouquets += 1
count = 0
return numOfBouquets
def minDays(self, bloomDay, m, k):
if len(bloomDay) < m * k:
return -1
start, end = 0, max(bloomDay)
minDays = -1
while start <= end:
mid = (start + end) // 2
if self.getNumOfBouquets(bloomDay, mid, k) >= m:
minDays = mid
end = mid - 1
else:
start = mid + 1
return minDays
Ставь 👍 и забирай 📚 Базу знаний