你能构造出连续值的最大数目 图解题解
这道题到底在问什么
- 输入
- coins=[1,3]
- 输出
- 2
- 输入
- coins=[1,1,1,4]
- 输出
- 8
- 输入
- coins=[1,4,10,3,1]
- 输出
- 20
最优解：一步一步想明白
- 3记牢一句:ans = 能连续凑出的金额个数(能凑 [0, ans-1]),从小到大拿硬币,v ≤ ans 就把它吃进来 ans += v,否则在 ans 处断开停手。下面每帧都在套这句。
- 4先看清画面。上面是原始硬币 [1,4,10,3,1],顺序是乱的。右边这块滚动状态记着我们最关心的量 ans,它表示从 0 开始已经能连续凑出多少个金额。什么硬币都不挑就能凑出金额 0,所以 ans 从 1 起步,此刻只能凑出 [0, 0] 这一个值。要往前推,第一件事是把硬币排好序。
- 5把硬币从小到大排成 [1,1,3,4,10]。为什么要从小的开始?排序的真正作用是让硬币面值一路不减:这样一旦某枚 v 超过当前 ans,后面所有硬币都不小于 v、也就都大于 ans,金额 ans 真的谁也补不出,才能放心停手。如果不排序,可能先撞上那枚 10,把本来后面几枚小硬币还能填的位置误判成缺口,过早停错。排好序,ans 还是 1,准备从最左边这枚 1 开始一枚枚吃进来。
- 6正式开始前把起点钉牢。现在一枚硬币都还没吃进来,能凑出的只有金额 0,也就是能凑区间 [0, 0],连续值个数 ans 等于 1。接下来每吃进一枚硬币,如果不留缺口,这个区间就往右扩,ans 也跟着变大。目标是把五枚硬币尽量都吃进来。
- 7看最左边这枚待考察的硬币,记住贯穿全程的判定规则。当前能凑 [0, ans-1],最大凑到 ans-1。再添一枚面值 v,它能补出的最小新金额正好是 v。要想不留窟窿,v 必须不能越过已经铺好的地面往前跳,也就是 v 要小于等于 ans。只要 v ≤ ans,新旧两段就严丝合缝连起来;一旦 v 比 ans 还大,金额 ans 这个位置谁都凑不出,后面全断,只能停手。下面就拿这把尺子一枚枚量。
- 8轮到最小的第 1 枚硬币,面值是 1。此刻还没吃任何硬币,ans = 1,能凑的只有 [0, 0]。先把它拎出来,看看这枚 1 能不能无缝接上去。
- 9拿尺子一量:面值 1 小于等于当前 ans = 1,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
- 10把这枚 1 正式吃进来(标绿),它能凑出的 [1, 1] 和原来的 [0, 0] 拼成一整片。ans 从 1 加上 1 变成 2,现在从 0 到 1 每个金额都能凑出来。继续看下一枚。
- 11轮到第 2 枚硬币,面值是 1。前面 1 枚已经吃进来(蓝色),把 ans 推到了 2,现在能凑 [0, 1]。先把它拎出来,看看这枚 1 能不能无缝接上去。
- 12拿尺子一量:面值 1 小于等于当前 ans = 2,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
- 13把这枚 1 正式吃进来(标绿),它能凑出的 [1, 2] 和原来的 [0, 1] 拼成一整片。ans 从 2 加上 1 变成 3,现在从 0 到 2 每个金额都能凑出来。继续看下一枚。
- 14轮到第 3 枚硬币,面值是 3。前面 2 枚已经吃进来(蓝色),把 ans 推到了 3,现在能凑 [0, 2]。先把它拎出来,看看这枚 3 能不能无缝接上去。
- 15拿尺子一量:面值 3 小于等于当前 ans = 3,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
- 16把这枚 3 正式吃进来(标绿),它能凑出的 [3, 5] 和原来的 [0, 2] 拼成一整片。ans 从 3 加上 3 变成 6,现在从 0 到 5 每个金额都能凑出来。继续看下一枚。
- 17轮到第 4 枚硬币,面值是 4。前面 3 枚已经吃进来(蓝色),把 ans 推到了 6,现在能凑 [0, 5]。先把它拎出来,看看这枚 4 能不能无缝接上去。
- 18拿尺子一量:面值 4 小于等于当前 ans = 6,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
- 19把这枚 4 正式吃进来(标绿),它能凑出的 [4, 9] 和原来的 [0, 5] 拼成一整片。ans 从 6 加上 4 变成 10,现在从 0 到 9 每个金额都能凑出来。继续看下一枚。
- 20轮到第 5 枚硬币,面值是 10。前面 4 枚已经吃进来(蓝色),把 ans 推到了 10,现在能凑 [0, 9]。先把它拎出来,看看这枚 10 能不能无缝接上去。
- 21拿尺子一量:面值 10 小于等于当前 ans = 10,满足 v ≤ ans。既然它没有越过已经铺好的地面,新旧两段金额就能严丝合缝地接起来,不会留窟窿。这枚可以放心吃进来。
- 22把这枚 10 正式吃进来(标绿),它能凑出的 [10, 19] 和原来的 [0, 9] 拼成一整片。ans 从 10 加上 10 变成 20,现在从 0 到 19 每个金额都能凑出来。五枚硬币全部吃进,循环结束。
- 23随手抽查几个金额验证一下。13 就是 10 加 3,19 是 10 加 4 加 3 加 1 加 1,一路数下来 0 到 19 里的每个整数都能挑出一组硬币凑出来。那 20 呢?五枚硬币加起来总和才 19,连凑都凑不满 20,所以最大只能连续到 19。能连续凑出的正好是 0 到 19 这 20 个金额。
- 24回看整条路:排好序 [1,1,3,4,10],ans 从 1 起步,每枚硬币都满足 v ≤ ans,于是依次把 ans 推到 2、3、6、10,最后加上 10 冲到 20。整道题的窍门就一句:从小到大拿硬币,能接上就吃进来 ans += v,接不上就停。最终答案 20。
⚠️ 容易写错的地方
✗ 错：不排序就直接套「v 大于 ans 就停」的停手规则(乱序时会提前撞上大硬币误判缺口)
✓ 对：一定先从小到大排序,再从最小的硬币逐枚吃进来
「v 大于 ans 就停」这条停手规则只有在硬币从小到大排好序时才成立:排序后一旦 v 超过 ans,剩下的硬币都不小于 v、更大于 ans,金额 ans 确实谁也补不出,停得对。若乱序,可能先撞上一枚大硬币就误判缺口提前停,而后面本还有小硬币能把这个位置填上,ans 会被算小甚至算错。排序是这套贪心成立的前提
✗ 错：把判定写成 v ≤ ans-1(即 v 严格小于 ans),漏掉 v 正好等于 ans 的情况
✓ 对：判定条件是 v ≤ ans,等号必须取到
当前能凑到最大值 ans-1,再添一枚 v = ans 时,它能补出的最小新金额正好是 ans,恰好接在 ans-1 后面,两段严丝合缝,应当吃进来。若写成 v ≤ ans-1 就会在这里提前停,把本该能凑的金额漏掉,答案偏小。参考代码写成「v 大于 ans 才 break」,正是包含了 v = ans 继续累加
✗ 错：ans 初始值写成 0,导致第一枚硬币的判定和最终计数全部错位
✓ 对：ans 必须初始化为 1
什么硬币都不挑就能凑出金额 0,这本身就是一个能凑出的连续值,所以起点是「能凑 1 个值」,ans = 1。若写成 0,第一枚哪怕是面值 1 的硬币也会因为 1 大于 0 而被误判成缺口直接停,答案恒为 0,彻底错
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int getMaximumConsecutive(vector<int>& coins) {
sort(coins.begin(), coins.end());
int ans = 1;
for (int& v : coins) {
if (v > ans) break;
ans += v;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int getMaximumConsecutive(int[] coins) {
Arrays.sort(coins);
int ans = 1;
for (int v : 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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 你能构造出连续值的最大数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么严格说清这个贪心是对的,不是凑巧?+
用循环不变式来证。不变式是:每处理完一批硬币,ans 恰好等于「用这些硬币从 0 开始能连续凑出的金额个数」,即能凑 [0, ans-1] 里每一个整数、且凑不出 ans。起点空集能凑出 0,ans = 1,成立。归纳一步:硬币已排序,当前能凑 [0, ans-1],来了枚不小于之前所有已用硬币的 v。若 v ≤ ans,原区间 [0, ans-1] 与新加的 [v, v+ans-1] 因为 v 不超过 ans 而首尾相接,合并成 [0, ans+v-1],新的连续个数正好是 ans+v,不变式保持;若 v 大于 ans,金额 ans 没有任何子集能凑出(所有还没用的硬币都不小于 v、更大于 ans),缺口坐实,ans 就是最终答案。所以贪心每一步都严格维持了这个不变式,结论正确。
ans 会不会溢出,要不要用 long?+
看数据范围。本题里硬币枚数和每枚面值都不超过四万上下,所有硬币加起来最多在十六亿这个量级,而 ans 最大也就是全部吃进来时的总和加一,同样在十六亿附近,没有越过 int 大约二十一亿的上界,所以参考代码三种语言都用 int 就够。但如果把面值或枚数放大,比如面值到十亿、枚数到十万,总和轻松突破 int,这时就必须换成 long long 或 long 防溢出。面试时主动补一句「当前约束 int 够用,放大范围要换 long」会显得考虑周全。
如果不是问连续个数,而是问某个具体金额能不能凑出,思路一样吗?+
那是另一类问题,通常不能只靠这套贪心。问「特定金额能否用子集凑出」本质是子集和问题,一般用背包式的动态规划:开一个布尔数组标记每个金额可达与否,逐枚硬币更新。本题特殊在只关心「从 0 起连续覆盖到哪」,这个连续性让我们能用一个滚动的 ans 代替整张可达表,把空间从背包的 O(总金额) 压到 O(1),时间也只需排序加一遍扫描。识别出「连续」这个特性,是能用贪心而不必上背包的关键。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 你能构造出连续值的最大数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。