跳至主要內容

1833. 雪糕的最大数量

ITCharge大约 1 分钟

1833. 雪糕的最大数量open in new window

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

题目链接

题目大意

描述:给定一个数组 costscosts 表示不同雪糕的定价,其中 costs[i]costs[i] 表示第 ii 支雪糕的定价。再给定一个整数 coinscoins 表示 Tony 一共有的现金数量。

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

说明

  • costs.length==ncosts.length == n
  • 1n1051 \le n \le 10^5
  • 1costs[i]1051 \le costs[i] \le 10^5
  • 1coins1081 \le coins \le 10^8

示例

  • 示例 1:
输入:costs = [1,3,2,4,1], coins = 7
输出:4
解释:Tony 可以买下标为 0124 的雪糕,总价为 1 + 3 + 2 + 1 = 7
  • 示例 2:
输入:costs = [10,6,8,7,7,8], coins = 5
输出:0
解释:Tony 没有足够的钱买任何一支雪糕。

解题思路

思路 1:排序 + 贪心

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

  1. 对数组 costscosts 进行排序。
  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×log2n)O(n \times \log_2n)
  • 空间复杂度O(1)O(1)