题目描述
思路解析动画文字版
记牢一句:ans = 能连续凑出的金额个数(能凑 [0, ans-1]),从小到大拿硬币,v ≤ ans 就把它吃进来 ans += v,否则在 ans 处断开停手。下面每帧都在套这句。
总览 · 原始硬币未排序：先看清画面。上面是原始硬币 [1,4,10,3,1],顺序是乱的。右边这块滚动状态记着我们最关心的量 ans,它表示从 0 开始已经能连续凑出多少个金额。什么硬币都不挑就能凑出金额 0,所以 ans 从 1 起步,此刻只能凑出 [0, 0] 这一个值。要往前推,第一件事是把硬币排好序。
排序 · 从小到大 [1,1,3,4,10]：把硬币从小到大排成 [1,1,3,4,10]。为什么要从小的开始?排序的真正作用是让硬币面值一路不减:这样一旦某枚 v 超过当前 ans,后面所有硬币都不小于 v、也就都大于 ans,金额 ans 真的谁也补不出,才能放心停手。如果不排序,可能先撞上那枚 10,把本来后面几枚小硬币还能填的位置误判成缺口,过早停错。排好序,ans 还是 1,准备从最左边这枚 1 开始一枚枚吃进来。
起点 · ans = 1,能凑 [0, 0]：正式开始前把起点钉牢。现在一枚硬币都还没吃进来,能凑出的只有金额 0,也就是能凑区间 [0, 0],连续值个数 ans 等于 1。接下来每吃进一枚硬币,如果不留缺口,这个区间就往右扩,ans 也跟着变大。目标是把五枚硬币尽量都吃进来。
规则 · v ≤ ans 才无缺口：看最左边这枚待考察的硬币,记住贯穿全程的判定规则。当前能凑 [0, ans-1],最大凑到 ans-1。再添一枚面值 v,它能补出的最小新金额正好是 v。要想不留窟窿,v 必须不能越过已经铺好的地面往前跳,也就是 v 要小于等于 ans。只要 v ≤ ans,新旧两段就严丝合缝连起来;一旦 v 比 ans 还大,金额 ans 这个位置谁都凑不出,后面全断,只能停手。下面就拿这把尺子一枚枚量。
第 1 枚 · 考察 v = 1：轮到最小的第 1 枚硬币,面值是 1。此刻还没吃任何硬币,ans = 1,能凑的只有 [0, 0]。先把它拎出来,看看这枚 1 能不能无缝接上去。
第 1 枚 · 判定 1 ≤ 1：拿尺子一量:面值 1 小于等于当前 ans = 1,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
第 1 枚 · 扩张 ans = 2：把这枚 1 正式吃进来(标绿),它能凑出的 [1, 1] 和原来的 [0, 0] 拼成一整片。ans 从 1 加上 1 变成 2,现在从 0 到 1 每个金额都能凑出来。继续看下一枚。
第 2 枚 · 考察 v = 1：轮到第 2 枚硬币,面值是 1。前面 1 枚已经吃进来(蓝色),把 ans 推到了 2,现在能凑 [0, 1]。先把它拎出来,看看这枚 1 能不能无缝接上去。
第 2 枚 · 判定 1 ≤ 2：拿尺子一量:面值 1 小于等于当前 ans = 2,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
第 2 枚 · 扩张 ans = 3：把这枚 1 正式吃进来(标绿),它能凑出的 [1, 2] 和原来的 [0, 1] 拼成一整片。ans 从 2 加上 1 变成 3,现在从 0 到 2 每个金额都能凑出来。继续看下一枚。
第 3 枚 · 考察 v = 3：轮到第 3 枚硬币,面值是 3。前面 2 枚已经吃进来(蓝色),把 ans 推到了 3,现在能凑 [0, 2]。先把它拎出来,看看这枚 3 能不能无缝接上去。
第 3 枚 · 判定 3 ≤ 3：拿尺子一量:面值 3 小于等于当前 ans = 3,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
第 3 枚 · 扩张 ans = 6：把这枚 3 正式吃进来(标绿),它能凑出的 [3, 5] 和原来的 [0, 2] 拼成一整片。ans 从 3 加上 3 变成 6,现在从 0 到 5 每个金额都能凑出来。继续看下一枚。
第 4 枚 · 考察 v = 4：轮到第 4 枚硬币,面值是 4。前面 3 枚已经吃进来(蓝色),把 ans 推到了 6,现在能凑 [0, 5]。先把它拎出来,看看这枚 4 能不能无缝接上去。
第 4 枚 · 判定 4 ≤ 6：拿尺子一量:面值 4 小于等于当前 ans = 6,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
第 4 枚 · 扩张 ans = 10：把这枚 4 正式吃进来(标绿),它能凑出的 [4, 9] 和原来的 [0, 5] 拼成一整片。ans 从 6 加上 4 变成 10,现在从 0 到 9 每个金额都能凑出来。继续看下一枚。
第 5 枚 · 考察 v = 10：轮到第 5 枚硬币,面值是 10。前面 4 枚已经吃进来(蓝色),把 ans 推到了 10,现在能凑 [0, 9]。先把它拎出来,看看这枚 10 能不能无缝接上去。
第 5 枚 · 判定 10 ≤ 10：拿尺子一量:面值 10 小于等于当前 ans = 10,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
第 5 枚 · 扩张 ans = 20：把这枚 10 正式吃进来(标绿),它能凑出的 [10, 19] 和原来的 [0, 9] 拼成一整片。ans 从 10 加上 10 变成 20,现在从 0 到 19 每个金额都能凑出来。五枚硬币全部吃进,循环结束。
验证 · 0 到 19 都能凑出：随手抽查几个金额验证一下。13 就是 10 加 3,19 是 10 加 4 加 3 加 1 加 1,一路数下来 0 到 19 里的每个整数都能挑出一组硬币凑出来。那 20 呢?五枚硬币加起来总和才 19,连凑都凑不满 20,所以最大只能连续到 19。能连续凑出的正好是 0 到 19 这 20 个金额。
完成 · 答案 = 20：回看整条路:排好序 [1,1,3,4,10],ans 从 1 起步,每枚硬币都满足 v ≤ ans,于是依次把 ans 推到 2、3、6、10,最后加上 10 冲到 20。整道题的窍门就一句:从小到大拿硬币,能接上就吃进来 ans += v,接不上就停。最终答案 20。
边界:[1,3] 只能凑 0 和 1(3 越过 ans = 2 断开);[2,4] 最小硬币 2 就跳空,答案 1;[1,1,1,4] 里 4 正好等于 ans = 4、等号取到吃进来,答案 8。
面试重点:用循环不变式证明贪心正确(ans 始终等于能连续凑出的金额个数);本题约束内 int 够用、放大要换 long;问「特定金额能否凑出」则是子集和背包、思路不同。
参考代码
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 getMaximumConsecutive(self, coins: List[int]) -> int: ans = 1 for v in sorted(coins): if v > ans: break ans += v return ans复杂度
- 时间：O(n log n)，n 是硬币枚数。主要开销在排序 O(n log n);排完之后只从左到右扫一遍,每枚硬币做一次比较加一次累加,是 O(n)。两者相加由排序主导,总体 O(n log n)。相比枚举所有子集去凑金额的指数级做法,这是质的飞跃
- 空间：O(log n) / O(n)，按峰值算,且只算排序带来的额外开销。算法本身只用了一个 ans 变量,是常数 O(1)。但排序要占额外空间:C++ 的 sort、Java 的 Arrays.sort 用递归快排,栈深 O(log n);Python 的 sorted 用 Timsort 且新建了一个列表,最坏 O(n)。所以峰值 C++ 与 Java 记 O(log n),Python 记 O(n)
易错点
面试追问把动画讲成自己的话
追问怎么严格说清这个贪心是对的,不是凑巧?
追问ans 会不会溢出,要不要用 long?
追问如果不是问连续个数,而是问某个具体金额能不能凑出,思路一样吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
雪糕的最大数量
LeetCode 1833 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题