题目描述
思路解析动画文字版
记牢一句:先把价格从小到大排序,从最便宜的一支支买,买得起(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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题