雪糕的最大数量

标签: 贪心 数组 排序

难度: Medium

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

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

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

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

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

提示：

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

Submission

运行时间: 81 ms

内存: 27.0 MB

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        N = max(costs)
        feq = [0] * (N+1)
        for c in costs:
            feq[c] += 1
        
        ans = 0
        for i in range(1, N+1):
            if feq[i] > 0:
                if coins <= feq[i] * i:
                    ans += coins // i
                    break
                coins -= feq[i] * i
                ans += feq[i]
        return ans

Explain

该题解采用了计数排序的思路来解决问题。首先，通过遍历雪糕价格数组，统计每个价格雪糕的数量，将这些信息存储在一个频率数组中。然后，从最便宜的雪糕开始，依次检查Tony能否购买当前价格的所有雪糕。如果可以，则更新剩余的金钱和已购买的雪糕数量；如果不可以，则计算在当前价格下，Tony最多能购买多少雪糕，并更新已购买的雪糕数量。这个过程一直进行，直到金钱用尽或检查完所有价格的雪糕。

时间复杂度: O(n + N)

空间复杂度: O(N)

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        N = max(costs)  # 找到costs中的最大值
        feq = [0] * (N+1)  # 创建频率数组，长度为最大值加1
        for c in costs:  # 统计每个价格雪糕的数量
            feq[c] += 1
        
        ans = 0  # 初始化已购买雪糕的数量
        for i in range(1, N+1):  # 从价格最低的雪糕开始遍历
            if feq[i] > 0:  # 如果当前价格的雪糕存在
                if coins < feq[i] * i:  # 如果剩余的钱不足以购买当前价格的所有雪糕
                    ans += coins // i  # 计算在当前价格下能购买的雪糕数量
                    break  # 退出循环
                coins -= feq[i] * i  # 更新剩余的金钱
                ans += feq[i]  # 更新已购买的雪糕数量
        return ans

Explore

计数排序在这个问题中被选择是因为它非常适合处理有限范围的整数数据。由于雪糕价格的范围通常不会非常广泛，计数排序可以在O(n + k)的时间内完成排序，其中n是雪糕的数量，k是价格的范围。相比之下，快速排序或归并排序通常需要O(n log n)的时间。此外，计数排序直接给出了每个价格的雪糕数量，便于后续直接根据价格和数量计算最大可购买数量，而不需要额外的数据结构或步骤。

如果coins的值非常小，甚至小于costs数组中的任何一个元素，算法仍然可以正确处理。在这种情况下，算法会从最便宜的雪糕开始尝试购买，但由于coins小于任何雪糕的价格，循环中的购买条件不会满足，因此购买数量ans将保持为0，代表没有购买任何雪糕。这体现了算法能够正确处理边界情况。

算法确保每种雪糕都尽可能多地被购买，直到雪糕或金钱用尽为止。在遍历完所有价格后，如果coins还有剩余，此时已没有更多雪糕可以购买，因此金钱的剩余是不可避免的。由于算法从最便宜的雪糕开始购买，因此已尽最大努力用最小的花费获取最多的雪糕，没有更好的方法来进一步利用剩余的coins，除非有更便宜的雪糕可以购买。

当costs数组中存在多个高频但价格昂贵的雪糕时，这种算法的效率依然是高效的，因为计数排序和随后的购买逻辑的时间复杂性仍然保持不变。然而，从效果上讲，由于这些雪糕价格较高，如果coins不足以购买足够数量的昂贵雪糕，那么可能无法最大化利用所有的coins来购买更多数量的雪糕。这种情况下，雪糕的购买数量可能会比拥有更多便宜雪糕的情况少。