题目描述
思路解析
一句话答案：LeetCode 1833 雪糕的最大数量：固定现金要买最多支，把价格从小到大排序、从最便宜的一支支买、买不起就停，先便宜换回的支数最多，时间 O(n log n)。
固定现金，买最多支雪糕，返回什么
给一个价格数组 costs，costs[i] 是第 i 支雪糕的价格，再给一笔现金 coins。可以按任意顺序挑任意几支，只要总价不超过 coins，目标是买到的支数最多，返回这个最大支数。题面 costs=[1,3,2,4,1]、coins=7，答案是 4；换成 costs=[10,6,8,7,7,8]、coins=5，最便宜的一支都要 6 元，一支也买不起，答案是 0。
手里就这么点钱，先挑哪几支
现金是死的，雪糕价格参差不齐，能塞进预算的组合多到数不清。要是随手先抱一支贵的走，比如那支 4 元的，一下就吃掉大半现金，剩的钱只够再添一两支便宜货，同一笔钱花在贵雪糕上换回的支数就少。把所有子集都枚举一遍去比最多支数，n 一大就爆，得找个不试遍所有组合的挑法。
为什么先买最便宜的一批，支数一定最多
目标是支数最多，不是把钱押在哪一支上，那每一块钱就该尽量多换雪糕。把价格从小到大排好，从最便宜的一支起往贵里买，支数就顶到头了。可以这样说服自己：假设某种买法买到了最多的 k 支，里头却有一支比某支它没买的还贵，把这支贵的退掉、换成那支更便宜的没买雪糕，花的钱只减不增，支数仍是 k，方案照样合法。这种替换一路做下去，最省钱的 k 支永远落在全场最便宜的那 k 支上——从便宜到贵地买，绝不会比别的买法买得少。
排序之后，一支支怎么买、何时收手
排完序从最便宜那支起，每支只问一句：手里的现金够不够付它。只要现金大于等于当前价格 c，就买下它，现金扣掉 c、已买支数加一，接着看下一支更贵的。等碰到第一支付不起的——现金比它的价格还少——就当场停手，此刻已买的支数就是答案。为什么不再往后翻翻能不能捡个便宜？价格已经从小到大排好，这支是没买的里最便宜的一支，连它都付不起，后面更贵的一定也付不起。
[1,3,2,4,1] 排完序，7 元买到第几支
先把 [1,3,2,4,1] 排成 [1,1,2,3,4]，现金 7 元、已买 0 支。第一支 1 元，7≥1 买下，剩 6 元、1 支；第二支 1 元，6≥1 买下，剩 5 元、2 支；第三支 2 元，5≥2 买下，剩 3 元、3 支；第四支 3 元，3≥3 正好付得起、花光现金买下，现金归零、4 支。轮到第五支 4 元，手里一分不剩付不起，停手。买到的正是最便宜的前四支、恰好花掉 7 元，得到 4 支。
几个写错就少买的地方，和它到底多快
不排序直接贪、或从贵的买起，会白白挤掉本可以拿的便宜支，支数算少。判定得用现金大于等于价格，等号要取到——现金恰好等于价格时花光也能拿下这一支，写成严格大于就会在钱数刚够时误判成买不起，少算一支。遇到第一支买不起别再往后翻找，排序后更贵的不可能反而买得起。
总时间是 O(n log n)，n 是雪糕支数——最重的就是排序这一步，压过后面那趟从便宜到贵、每支一次比较一次扣钱的线性扫描。价格有明确上限时改用计数排序，能把排序压到线性、总体降到 O(n+max)，买雪糕的逻辑一个字不用改。空间上只用现金和计数两个变量，额外开销都来自排序本身。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:先把价格从小到大排序,从最便宜的一支支买,买得起(coins ≥ c)就买下 count 加一,轮到买不起的那支就停,count 即答案。下面每帧都在套这句。
总览 · 原始价格未排序：先看清画面。上面是原始价格 [1,3,2,4,1],第 i 格就是第 i 支雪糕的价格,顺序是乱的。右边这块购买状态记着我们最关心的三个量:剩余现金此刻是 7 元,已买 0 支,一分钱还没花。要买到最多支数,第一件事是把价格排好序,让便宜的排在前面。
排序 · 从便宜到贵 [1,1,2,3,4]：把价格从小到大排成 [1,1,2,3,4]。为什么要从便宜的开始?因为目标是支数最多,不是省钱本身,而是让每一块钱换回尽量多的雪糕。同样一笔钱,先买便宜的能换到更多支。要是先花大价钱抢那支 4 元的,后面本可以买好几支便宜的机会就被挤掉了。排好序,现金还是 7 元,准备从最左边这支 1 元开始一支支买。
起点 · coins = 7,count = 0：正式开买之前把起点钉牢。现在一支雪糕都还没买,手里 7 元原封不动,已买支数 count 等于 0。接下来从最便宜的那支起,一支支往贵的方向走,买得起就买、现金减价格、count 加一,直到遇上一支买不起的为止。目标是尽量多买几支。
规则 · coins ≥ c 才买得起：盯住最左边这支待考察的雪糕,记住贯穿全程的那把尺子。每一步只问一句:手里剩的现金够不够付它的价格?只要剩余现金大于等于当前价格 c,就买得起,买下它,现金扣掉 c、count 加一。一旦剩的钱比当前这支还少,连排在最前的最便宜一支都付不起,那后面更贵的更别想,直接停。下面就拿这把尺子从 1 元那支一支支量过去。
第 1 支 · 考察 c = 1：轮到最便宜的第 1 支,价格是 1 元。此刻还没买任何雪糕,手里 7 元。先把它拎出来,看看手里这 7 元付不付得起这 1 元。
第 1 支 · 判定 7 ≥ 1：拿尺子一量:手里 7 元,大于等于这支的 1 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
第 1 支 · 买入 count = 1：把这支 1 元雪糕正式买下(标绿)。现金从 7 元付掉 1 元,剩 6 元;已买支数从 0 加到 1 支。接着看下一支更贵一点的。
第 2 支 · 考察 c = 1：轮到第 2 支,价格是 1 元。前面 1 支已经买下(蓝色),现金花到只剩 6 元,已买 1 支。先把它拎出来,看看手里这 6 元付不付得起这 1 元。
第 2 支 · 判定 6 ≥ 1：拿尺子一量:手里 6 元,大于等于这支的 1 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
第 2 支 · 买入 count = 2：把这支 1 元雪糕正式买下(标绿)。现金从 6 元付掉 1 元,剩 5 元;已买支数从 1 加到 2 支。接着看下一支更贵一点的。
第 3 支 · 考察 c = 2：轮到第 3 支,价格是 2 元。前面 2 支已经买下(蓝色),现金花到只剩 5 元,已买 2 支。先把它拎出来,看看手里这 5 元付不付得起这 2 元。
第 3 支 · 判定 5 ≥ 2：拿尺子一量:手里 5 元,大于等于这支的 2 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
第 3 支 · 买入 count = 3：把这支 2 元雪糕正式买下(标绿)。现金从 5 元付掉 2 元,剩 3 元;已买支数从 2 加到 3 支。接着看下一支更贵一点的。
第 4 支 · 考察 c = 3：轮到第 4 支,价格是 3 元。前面 3 支已经买下(蓝色),现金花到只剩 3 元,已买 3 支。先把它拎出来,看看手里这 3 元付不付得起这 3 元。
第 4 支 · 判定 3 ≥ 3：拿尺子一量:手里 3 元,大于等于这支的 3 元,买得起。注意这里现金和价格正好相等,3 元付 3 元刚好花光,这一支照样买得起、要算进去,这正是判定用大于等于、把等号取到的地方。把它买下来。
第 4 支 · 买入 count = 4：把这支 3 元雪糕正式买下(标绿)。现金从 3 元付掉 3 元,正好全部花光;已买支数从 3 加到 4 支。接着看下一支更贵一点的。
第 5 支 · 考察 c = 4：轮到第 5 支,价格是 4 元。前面 4 支已经买下(蓝色),现金已经花光,已买 4 支。先把它拎出来,看看手里已经一分不剩,还付不付得起这 4 元。
第 5 支 · 判定 0 < 4：拿尺子一量:手里的现金已经一分不剩,却要付 4 元,钱不够,这支买不起(标红)。前面 4 支便宜的已经把现金花得差不多了,轮到这支就付不起了。
停手 · 答案 count = 4：为什么这支买不起就能直接停,不用再看后面?因为价格已经从小到大排好,这支 4 元正是剩下里最便宜、也是唯一没买的一支(已标红)。连它都付不起,后面就算还有更贵的雪糕也一定买不起。所以到此为止,能买到的最大支数就锁定在 4 支。
验证 · 买 4 支花 7 元：回头验证一下这个答案。买下最便宜的前 4 支,价格是 1、1、2、3,一共 7 元,正好等于手里的 7 元,现金正好全部花光。剩下那支 4 元的(标红)确实买不起。想再多买一支是不可能的,因为便宜的都已经买光了,答案就是 4 支。
完成 · 答案 = 4：回看整条路:先把价格排成 [1,1,2,3,4],从最便宜的一支支买。1 元买下、又一个 1 元买下、2 元买下、3 元买下,现金正好花光,买到 4 支;轮到 4 元那支时钱不够,停手。整道题的窍门就一句:先排序,再从便宜到贵地买,买得起就买、买不起就停。最终答案 4。
边界:[10,6,8,7,7,8] coins=5 最便宜的 6 元都买不起,答案 0;[1,6,3,1,2,5] coins=20 现金富余全买下,答案 6;[2,4,3,5,2] coins=7 买 2、2、3 花光后停,答案 3。
面试重点:用交换论证证明先买最便宜的最优(把贵的换成更便宜的没买支,支数不减、花费更省);价格范围有限时可用计数排序把排序压到线性。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxIceCream(self, costs: List[int], coins: int) -> int: costs.sort() for i, c in enumerate(costs): if coins < c: return i coins -= c return len(costs)复杂度
- 时间：O(n log n)，n 是雪糕支数。主要开销在排序 O(n log n);排完之后只从便宜到贵扫一遍,每支做一次比较加一次现金累减,是 O(n)。两者相加由排序主导,总体 O(n log n)。若按题目提示改用计数排序,排序降到 O(n + max),总体可优化到线性,max 是最大价格
- 空间：O(log n) / O(n)，按峰值算,且只算排序带来的额外开销。算法本身只用现金与计数两个变量,是常数 O(1)。排序要占额外空间:C++ 的 sort、Java 的 Arrays.sort 用递归快排,栈深 O(log n);Python 的 sort 用 Timsort,最坏 O(n)。所以峰值 C++ 与 Java 记 O(log n),Python 记 O(n);若改计数排序则是 O(max)
易错点
面试追问把动画讲成自己的话
追问怎么证明「先买最便宜的」这个贪心一定能买到最多支数,而不是凑巧?
追问题目特意提示要用计数排序,和普通排序相比有什么区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
减小和重新排列数组后的最大元素
LeetCode 1846 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题