leetcode-1833. 雪糕的最大数量（排序+贪心）

题目链接:https://leetcode.cn/problems/maximum-ice-cream-bars/

思路

直观想法
在给定的硬币情况下，花最小的钱，买最多的雪糕，一眼贪心。

吐槽一句：这题mid难度有点离谱，easy题差不多，经典贪心题

算法

1. 对原雪糕价格 costs 数组进行小到大排序
2. 遍历 costs 数组，当前的雪糕价格不超过硬币数，则购买，直接减去当前雪糕价格，不用关心怎么搭配买最多，只管当前他最便宜我就买，贪心！

代码示例

func maxIceCream(costs []int, coins int) (ans int) {
    
	//go自带的排序x
    sort.Ints(costs)
    for i := range costs{
    
        if coins - costs[i] < 0{
    
            break
        }
        coins -= costs[i]
        ans++
    }
    return
}

复杂度分析

• 时间复杂度：O(n logn) 其中n 是数组 costs 的长度，对数组排序所需要的时间是O(n logn),遍历数组需要O(n)的时间，以上时间取最长则是O(n logn)
• 空间复杂度：O(logn)，其中 nn 是数组 costs 的长度。空间复杂度主要取决于排序使用的额外空间。