🎮 贪心扫货不迟疑，计数先求最大值

炎炎夏日，Tony同学热得快要融化了。他冲进雪糕店，发现货架上摆着n支雪糕，每支价格不同（costs[i]）。站在冰柜前，Tony双眼放光，脑海里只有一个声音在回荡：“买到最多数量的雪糕！”

但问题来了——Tony摸了摸口袋，只有 coins 块现金，如何在预算内实现雪糕自由？

第一幕：贪心的直觉

Tony的第一反应极其符合人类本能：买最便宜的！

这就好比下副本刷怪，你只有有限的血瓶（coins），小怪（便宜雪糕）攻击力低，你能多砍几只攒经验；Boss（贵雪糕）一刀暴击你就得回泉水读秒。贪心算法的核心教义就是——每次都做当前看似最优的选择，绝不回头，像个渣男。

于是Tony开始扫荡货架：

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()  # 排序，从白菜价到天价
        for i, cost in enumerate(costs):
            if coins < cost:  # 买不起了，GG
                return i
            coins -= cost  # 咬牙买下，钱包-1s
        return len(costs)  # 直接清空老板库存！

他抓着一大把雪糕就往收银台冲，嘴里还念叨着：“先买便宜的，剩下的钢镚儿还能凑一根，这波血赚！”

就在这时，柜台后面慢悠悠地探出一颗脑袋——雪糕店老板，一个穿着格子衫、发际线略显峥嵘的中年男人，鼻梁上架着那副仿佛焊死在脸上的黑框眼镜。

老板推了推眼镜，打量了Tony一番：“哟，小伙子，骨骼精奇啊！一眼就看穿了贪心的本质。不过嘛……”

Tony一愣：“不过啥？”

老板冷笑一声：“你有没有想过，如果雪糕价格范围很小，比如最贵的也就几块钱，你没必要把整个数组排序——O(n log n) 虽然不慢，但还有更骚的操作。”

Tony 眼睛一亮：”更骚的操作？“

老板诡谲一笑，吐出四个字：“计数排序（Counting Sort）。”

第二幕：计数排序——批发场景的神器

老板从柜台底下抽出一张皱巴巴的进货单，用圆珠笔在上面画了个表格：

场景：假设雪糕价格只有 1~5 块钱，n=100000。 普通排序：O(n log n) ≈ 100000 × 17 = 170万次比较。 计数排序：O(n + maxCost) ≈ 100000 + 5 = 10万次操作。

Tony眼睛都亮了：“快了一整个数量级？！”

老板扬了扬下巴：“没错。计数排序不比较大小，它数数——统计每个价格出现了多少次，然后从便宜到贵依次购买。就好比你玩抽卡游戏，管它具体是哪张卡呢，你只看‘1星有几张’、‘2星有几张’，然后从低到高无脑合成突破，这效率不就上来了？”

说罢，老板从柜台底下又摸出一把布满灰尘的机械键盘， C 和 V 键磨损严重，他手指像飞一样：

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        # 找到最贵的雪糕——决定桶的数量
        mx = max(costs)  
        # 开一个计数数组，像超市货架标签一样，每个价格一个格子
        cnt = [0] * (mx + 1)         
        for cost in costs:  
            cnt[cost] += 1
        
        # 从 1 块钱开始，按顺序扫货
        ans = 0  
        for cost in range(1, mx + 1):  
            if coins < cost:  # 钱不够买当前价格的雪糕了
                break
            num = min(cnt[cost], coins // cost)  # 预算能买得起几根？直接算出来
            coins -= num * cost  
            ans += num 
        return ans

Tony看得目瞪口呆：“ coins // price 直接批量采购，比我之前那 for 循环一根根买要快多了！用空间换时间，拿内存换执行速度，经典套路！”

老板满意地点头：“懂行！计数排序的精髓就是开个 count 数组存每个价格的出现次数，空间复杂度 O(maxCost)。价格区间越小，它越猛。我平时批发雪糕都是这么算的——不吹牛，进货单我从来不用计算器，脑子一跑计数排序，老板都得喊我一声‘人形自走ERP’。”

他顿了顿，语气突然变得语重心长：“不过嘛……要是敢把价格上限干到一亿，开个一亿长度的数组——那场面，内存当场就得给你报个 MemoryError。遇到这种情况，还是老老实实 sort() 吧。毕竟咱是来买雪糕的，不是来给服务器做压力测试的，对吧？”

第三幕：大佬的传说

Tony 捧着雪糕，忍不住问：“老板，你以前是干嘛的？这代码写得比我老师还溜。”

老板叹了口气，望向窗外的烈日，眼神仿佛穿透了雪糕店的天花板，伸向了遥远的服务器机房。

“我以前啊……” 老板缓缓摘下黑框眼镜，用格子衫的衣角擦了擦，“ 在某大厂干过七年，负责核心交易链路的库存系统。每年大促那天，全球几亿人同时抢购，我就得在毫秒之间算出‘最多能买多少件商品’——跟你今天这雪糕问题，本质一模一样，就是规模大了亿点点。”

Tony嘴里的冰棍差点掉下来：“卧槽，那你为啥跑来卖雪糕？”

老板重新戴上眼镜，嘴角抽搐了一下：“那年双十一，我为了优化一个排序模块，强行上计数排序，结果商品价格范围没估算好——有个奢侈品的价格是九千九百九十九万……我抬手就开了一个一亿长度的 count 数组，内存直接原地爆炸。整个订单系统卡了整整三秒钟。”

他顿了顿，拿起一根绿豆冰棍狠狠咬了一口：“三秒钟意味着什么？三秒钟足够用户截屏发微博骂你十八遍，足够竞品写一篇‘某厂又崩了’的公众号爆文，足够老板的脸色从猪肝色变成五彩斑斓的黑。第二天，HR就把我叫进小黑屋，递给我一张纸条，上面写着：‘感谢贡献，江湖再见’。”

Tony 听得头皮发麻：“所以你就拿着赔偿金开了雪糕店？”

老板摊了摊手：“不然呢？我面了一圈，面试官问我‘你上次线上事故的原因是什么’，我说‘计数排序数组开太大了’，然后就没了下文。后来我一想，算了，自己当老板吧。至少在这里，雪糕价格上限不会超过二十块，我手动写个 count[21] 的数组，内存绝对不会爆——爆了也就损失几根老冰棍，不至于让几亿人刷不出购物车。”

Tony啃着最后一根冰棍，若有所思：“所以——计数排序本身没毛病，错的是没先看一眼 max(costs)。”

老板一拍大腿：“你总算开窍了！先看最大值再决定用啥算法，前置防御式编程’，是我拿七年职业生涯换来的经验教训。你要记住——提前优化是万恶之源，但提前检查数据范围是保命之道。”

Tony郑重地点点头，把最后一口冰棍吞下去，含含糊糊地说：“懂了，明天我就把这句话刻在键盘上。”

这正是：

贪心扫货不迟疑，计数先求最大值。 老板当年爆内存，如今卖糕教解题。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。