Это душный летний день, и мальчик хочет купить батончики мороженого.
В магазине есть n
кафе-мороженое. Вам дан массив costs
длины n
, где costs[i]
— цена ith
плитки мороженого в монетах. У мальчика изначально есть coins
монет, и он хочет купить как можно больше батончиков мороженого.
Верните максимальное количество плиток мороженого, которое мальчик может купить заcoins
монет.
Примечание. Мальчик может покупать мороженое в любом порядке.
Пример 1:
Input: costs = [1,3,2,4,1], coins = 7 Output: 4 Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.
Пример 2:
Input: costs = [10,6,8,7,7,8], coins = 5 Output: 0 Explanation: The boy cannot afford any of the ice cream bars.
Пример 3:
Input: costs = [1,6,3,1,2,5], coins = 20 Output: 6 Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.
Ограничения:
costs.length == n
1 <= n <= 10^5
1 <= costs[i] <= 10^5
1 <= coins <= 10^8
Интуиция
Задача состоит в том, чтобы найти максимальное количество шоколадок, которое может получить мальчик в пределах лимита монет. Так что, чтобы шоколадок было по максимуму, всегда оптимально покупать плитки шоколада по небольшой цене. Таким образом, мы можем отсортировать массив издержек и просто продолжать проверять, можно ли купить текущую шоколадку с деньгами на руках.
Подход
- Отсортируйте массив.
- Пройдите через массив, сохраняя текущую сумму.
- Увеличьте текущую сумму на стоимость и проверьте, меньше ли текущая сумма предела стоимости или равна ему. Если да, то мы можем купить эту плитку шоколада, иначе мы остановимся.
- После выхода из массива верните количество плиток шоколада.
Сложность
- Временная сложность:
Мы сортируем массив, а также просматриваем массив один раз.
Таким образом, временная сложность будет O(nlogn) + O(n), где n = длина массива. - Сложность пространства:
Сортировка может занимать некоторое пространство. Но кроме этого, мы не используем дополнительное пространство. Таким образом, пространственная сложность будет O (1)
Код
class Solution { public int maxIceCream(int[] costs, int coins) { int length = costs.length; // eventhough the constraint starts from 1, // just adding as part of practice if (length == 0 || costs == null) { return 0; } if (coins <= 0) { return 0; } Arrays.sort(costs); int runningSum = 0; int chocolateBar = 0; for (int num : costs) { runningSum += num; if (runningSum <= coins) { chocolateBar++; } else { break; } } return chocolateBar; } }
Пожалуйста, не стесняйтесь предлагать лучший подход или другой подход к той же проблеме. Кроме того, поправьте меня, если у меня есть какие-либо ошибки.
Спасибо.