[LeetCode] 1833. Maximum Ice Cream Bars

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 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.

Example 2:
Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 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.

Constraints:
costs.length == n
1 <= n <= 105
1 <= costs[i] <= 105
1 <= coins <= 108

雪糕的最大数量。

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

注意：Tony 可以按任意顺序购买雪糕。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-ice-cream-bars
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是 counting sort 计数排序，这是题目要求。当然这道题也可以用排序做。

我们创建一个 map 数组，长度为 100001，这是 input data 给的最大值，然后开始遍历 input 数组，记录每个单价不同的雪糕分别有几个。再次遍历 map 数组，从单价最小的元素开始，如果当前雪糕的单价 map[i] 小于目前手里的 coins，意味着我们可以起码买一个当前单价的雪糕。对于当前单价的这种雪糕，我们能买的数量 = Math.min(coins / map[i], map[i])，意思是 coins 能买的数量和这个单价的雪糕的数量的最小值。这里容易忽略。举个例子，比如你有 400 块，单价 2 块的雪糕只有 1 个，你能买的单价 2 块的雪糕也有只有 1 个而不是 200 个。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int[] map = new int[100001];
        int max = -1;
        for (int cost : costs) {
            map[cost]++;
            max = Math.max(max, cost);
        }

        int res = 0;
        for (int i = 1; i <= max; i++) {
			// 如果钱花完了就直接退出
            if (coins <= 0) {
                break;
            }
			// 如果当前单价的雪糕还有并且我手里还有钱
            if (map[i] != 0 && coins >= i) {
				// 可以购买的数量
                int count = Math.min(coins / i, map[i]);
                map[i] -= count;
                res += count;
                coins -= i * count;
            }
        }
        return res;
    }
}