Это душный летний день, и мальчик хочет купить батончики мороженого.

В магазине есть 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

Интуиция

Задача состоит в том, чтобы найти максимальное количество шоколадок, которое может получить мальчик в пределах лимита монет. Так что, чтобы шоколадок было по максимуму, всегда оптимально покупать плитки шоколада по небольшой цене. Таким образом, мы можем отсортировать массив издержек и просто продолжать проверять, можно ли купить текущую шоколадку с деньгами на руках.

Подход

  1. Отсортируйте массив.
  2. Пройдите через массив, сохраняя текущую сумму.
  3. Увеличьте текущую сумму на стоимость и проверьте, меньше ли текущая сумма предела стоимости или равна ему. Если да, то мы можем купить эту плитку шоколада, иначе мы остановимся.
  4. После выхода из массива верните количество плиток шоколада.

Сложность

  • Временная сложность:
    Мы сортируем массив, а также просматриваем массив один раз.
    Таким образом, временная сложность будет 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;
    }
}

Пожалуйста, не стесняйтесь предлагать лучший подход или другой подход к той же проблеме. Кроме того, поправьте меня, если у меня есть какие-либо ошибки.
Спасибо.