1833. 雪糕的最大数量

• 标签：贪心、数组、排序
• 难度：中等

题目链接

• 1833. 雪糕的最大数量 - 力扣

题目大意

描述：给定一个数组 $costs$ 表示不同雪糕的定价，其中 $costs[i]$ 表示第 $i$ 支雪糕的定价。再给定一个整数 $coins$ 表示 Tony 一共有的现金数量。

要求：计算并返回 Tony 用 $coins$ 现金能够买到的雪糕的最大数量。

说明：

• $costs.length == n$。
• $1 \le n \le 10^5$。
• $1 \le costs[i] \le 10^5$。
• $1 \le coins \le 10^8$。

示例：

• 示例 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 没有足够的钱买任何一支雪糕。

解题思路

思路 1：排序 + 贪心

贪心思路，如果想尽可能买到多的雪糕，就应该优先选择价格便宜的雪糕。具体步骤如下：

1. 对数组 $costs$ 进行排序。
2. 按照雪糕价格从低到高开始买雪糕，并记录下购买雪糕的数量，知道现有钱买不起雪糕为止。
3. 输出购买雪糕的数量作为答案。

思路 1：代码

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        ans = 0
        for cost in costs:
            if coins >= cost:
                ans += 1
                coins -= cost
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log_2n)$。
• 空间复杂度：$O(1)$。