你能构造出连续值的最大数目 图解题解

从 0 开始，连续能凑出几个金额

给一把硬币，第 i 枚面值 coins[i]，面值可能重复。任意挑一部分，它们的和就是能凑出的一个金额；什么都不挑和是 0。问从 0 起最多能连续凑出多少个整数金额。题面 coins=[1,3] 只能凑 0 和 1、返回 2，金额 2 就断在这里；coins=[1,1,1,4] 返回 8。问的是从 0 连续覆盖到哪，不是某个具体金额能不能拼。

挨个子集去试，为什么试不起

n 枚硬币能挑出 2 的 n 次方个子集，把每个子集的和算出来标记可达金额，这是能直接想到的暴力，可 n 到二三十就是上亿个子集，枚举不完。就算改用背包式可达标记，也得开一张覆盖所有金额的表逐枚更新，没利用上从 0 连续覆盖这个特点。

排序之后，新硬币凭什么能接上去

先把硬币从小到大排好，盯住一个量：眼下已能连续凑出的最大金额，叫它上界。什么都不挑只能凑出 0，上界就是 0，能凑 [0, 0]。排好序后逐枚考察，轮到的这枚 v 一定不小于前面用过的硬币；它新变出的金额是在每个可凑金额上再加一个 v，等于把 [0, 上界] 平移成 [v, v+上界]。

两段要接成一条不断的区间，[v, v+上界] 的左端 v 就不能越过 [0, 上界] 的右端太远：只要 v ≤ 上界+1，v 落在上界右边紧挨一格或和旧区间重叠，两段并成 [0, v+上界]，上界扩到 v+上界。可一旦 v ＞ 上界+1，金额上界+1 被跳过去，这枚 v 起步就在它右边，谁也补不出，连续到此为止。排序是前提：面值一路不减，越界这枚之后再没更小的能回头填坑；乱序会先撞上大硬币误判缺口。

落到代码：ans 从 1 起，v ＞ ans 就停

上界加 1 就是下面代码里的 ans。参考代码不另设上界，直接记 ans = 能连续凑出的金额个数，也就是上界加一：空集能凑出 0，所以 ans 从 1 起步、不是 0，写成 0 第一枚哪怕面值 1 也会被当缺口、答案恒卡 0。判定换到 ans 上就是 v ≤ ans，代码写作 v ＞ ans 就 break，把 v 等于 ans 的那枚留下继续吃：它补出的最小新金额恰好是 ans，接在 ans-1 后面严丝合缝，等号非取到不可，写成 v ≤ ans-1 会提前停、漏掉金额。满足就 ans += v，遍历完返回 ans。整体时间 O(n log n)，排序最重，扫描 O(n) 不改量级；额外只用一个 ans，空间 O(1)。

把 [1,4,10,3,1] 从头滚一遍 ans

拿题面 coins=[1,4,10,3,1]，排序成 [1,1,3,4,10]，ans 从 1 起步、能凑 [0,0]。第一枚 1 不大于 ans=1，ans 变 2；第二枚 1 不大于 2，ans 变 3；第三枚 3 正好等于 ans=3、等号取到，ans 变 6；第四枚 4 不大于 6，ans 变 10；第五枚 10 等于 ans=10，ans 变 20，0 到 19 都能凑。硬币用完返回 ans = 20，五枚总和才 19、连 20 都凑不满，答案就是 0 到 19 这 20 个值。

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 ans

C++

#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;
    }
}