Сложность: easy
У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.
Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину.
Пример:
Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.
👨💻 Алгоритм:
1⃣Преобразование массива в мин-кучу:
Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.
2⃣Инициализация переменных:
Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.
3⃣Добавление яблок в корзину:
Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:
Увеличивайте apples на 1.
Увеличивайте units на значение, извлеченное из кучи.
😎 Решение:
class Solution {
public int maxNumberOfApples(int[] arr) {
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
Queue<Integer> heap = new PriorityQueue<>(list);
int apples = 0, units = 0;
while (!heap.isEmpty() && units + heap.peek() <= 5000) {
units += heap.remove();
apples += 1;
}
return apples;
}
}Ставь 👍 и забирай 📚 Базу знаний