摘要:
排序+贪心题。
题目
夏日炎炎,小男孩 Tony 想买一些雪糕消消暑。
商店中新到
给你价格数组
注意:Tony 可以按任意顺序购买雪糕。
示例 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 。
提示:
贪心+计数排序
因为数组中数值存在一个范围,那么我们可以用计数排序的方法优化排序的复杂度为线性。
按照价格升序选择雪糕,最终个数一定是最多的。
1 | class Solution { |
原题链接: LeetCode 1833. 雪糕的最大数量