Medium

题目描述

炎炎夏日，一个小男孩想要购买一些冰淇淋。

商店里有 n 根冰淇淋，给你一个长度为 n 的数组 costs，其中 costs[i] 是第 i 根冰淇淋的价格（以硬币为单位）。这个男孩最初有 coins 枚硬币可以花费，他想要购买尽可能多的冰淇淋。

注意：男孩可以按任意顺序购买冰淇淋。

返回这个男孩用 coins 枚硬币能够购买的最大冰淇淋数量。

你必须使用计数排序来解决这个问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：这个男孩可以购买索引为 0,1,2,4 的冰淇淋，总价格为 1 + 3 + 2 + 1 = 7。

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：这个男孩买不起任何冰淇淋。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：这个男孩可以购买所有的冰淇淋，总价格为 1 + 6 + 3 + 1 + 2 + 5 = 18。

约束条件：

  • costs.length == n
  • 1 <= n <= 10^5
  • 1 <= costs[i] <= 10^5
  • 1 <= coins <= 10^8

提示：

  • 总是优先购买最便宜的冰淇淋是最优的。
  • 对价格进行排序，使最便宜的冰淇淋排在前面。

解题思路

解题思路

这是一个典型的贪心算法问题。要想用有限的硬币买到最多的冰淇淋，显然应该优先购买价格最便宜的冰淇淋。

解法分析

贪心策略： 按价格从小到大排序，然后依次购买最便宜的冰淇淋，直到硬币不足为止。

排序方法选择：

  1. 普通排序：使用快排等通用排序算法，时间复杂度 O(n log n)
  2. 计数排序：题目要求使用计数排序，适用于数据范围有限的情况，时间复杂度 O(n + k)，其中 k 是价格的最大值

由于题目明确要求使用计数排序，且价格范围在 1 到 10^5 之间，计数排序是很好的选择。

计数排序实现步骤

  1. 统计每个价格出现的次数
  2. 按价格从小到大遍历，尽可能多地购买每个价格的冰淇淋
  3. 当硬币不足时停止购买

这种方法既满足了题目要求，又能达到最优的时间复杂度。

代码实现

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        vector<int> count(100001, 0);
        
        // 计数排序：统计每个价格出现的次数
        for (int cost : costs) {
            count[cost]++;
        }
        
        int result = 0;
        // 从最便宜的开始购买
        for (int price = 1; price <= 100000 && coins > 0; price++) {
            if (count[price] > 0) {
                // 计算能买多少个这个价格的冰淇淋
                int canBuy = min(count[price], coins / price);
                result += canBuy;
                coins -= canBuy * price;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        # 计数排序：统计每个价格出现的次数
        count = [0] * 100001
        
        for cost in costs:
            count[cost] += 1
        
        result = 0
        # 从最便宜的开始购买
        for price in range(1, 100001):
            if coins <= 0:
                break
            if count[price] > 0:
                # 计算能买多少个这个价格的冰淇淋
                can_buy = min(count[price], coins // price)
                result += can_buy
                coins -= can_buy * price
        
        return result

public class Solution {
    public int MaxIceCream(int[] costs, int coins) {
        int[] count = new int[100001];
        
        // 计数排序：统计每个价格出现的次数
        foreach (int cost in costs) {
            count[cost]++;
        }
        
        int result = 0;
        // 从最便宜的开始购买
        for (int price = 1; price <= 100000 && coins > 0; price++) {
            if (count[price] > 0) {
                // 计算能买多少个这个价格的冰淇淋
                int canBuy = Math.Min(count[price], coins / price);
                result += canBuy;
                coins -= canBuy * price;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} costs
 * @param {number} coins
 * @return {number}
 */
var maxIceCream = function(costs, coins) {
    const count = new Array(100001).fill(0);
    
    // 计数排序：统计每个价格出现的次数
    for (const cost of costs) {
        count[cost]++;
    }
    
    let result = 0;
    // 从最便宜的开始购买
    for (let price = 1; price <= 100000 && coins > 0; price++) {
        if (count[price] > 0) {
            // 计算能买多少个这个价格的冰淇淋
            const canBuy = Math.min(count[price], Math.floor(coins / price));
            result += canBuy;
            coins -= canBuy * price;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型普通排序解法计数排序解法（推荐）
时间复杂度O(n log n)O(n + k)
空间复杂度O(1)O(k)

其中 n 是冰淇淋数量，k 是价格的最大值（题目中为 10^5）。

说明：

  • 计数排序解法的时间复杂度更优，特别是当 k 相对较小时
  • 计数排序需要额外的 O(k) 空间来存储计数数组
  • 题目明确要求使用计数排序，因此推荐使用计数排序解法