[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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题不难，我提供两种思路。一是排序，二是计数排序。

方法一需要对 input 数组排序，排序过后，单价小的雪糕排在前面，我们就可以用手上的现金数量去比较当前雪糕的单价，看是否能买，不能买的时候就可以直接 break 并返回能买的数量。

时间O(nlogn)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxIceCream(int[] costs, int coins) {
 3         Arrays.sort(costs);
 4         int count = 0;
 5         for (int i = 0; i < costs.length; i++) {
 6             if (coins - costs[i] >= 0) {
 7                 coins -= costs[i];
 8                 count++;
 9             } else {
10                 break;
11             }
12         }
13         return count;
14     }
15 }

方法二计数排序，时间复杂度更好，但是代价是有额外空间。我们创建一个 map 数组记录每个单价不同的雪糕分别有多少个。数组的下标代表雪糕的单价，数组内任意一个 map[i] 的值代表某个单价的雪糕有几个。然后我们遍历 map 数组，看看手上的现金能买多少个雪糕。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int maxIceCream(int[] costs, int coins) {
 3         int max = 0;
 4         for (int cost : costs) {
 5             max = Math.max(max, cost);
 6         }
 7 
 8         int count = 0;
 9         int[] map = new int[max + 1];
10         for (int cost : costs) {
11             map[cost]++;
12         }
13 
14         for (int i = 0; i <= max; i++) {
15             if (map[i] == 0) {
16                 continue;
17             }
18             if (i > coins) {
19                 break;
20             } else {
21                 for (int j = 0; j < map[i]; j++) {
22                     if (i > coins) {
23                         break;
24                     } else {
25                         count++;
26                         coins -= i;
27                     }
28                 }
29             }
30         }
31         return count;
32     }
33 }

LeetCode 题目总结