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

难度: Medium

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以构造出 x 。

请返回从 0 开始（包括 0 ），你最多能构造出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 2 个连续整数。

示例 2：

输入：coins = [1,1,1,4]
输出：8
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
- 2：取 [1,1]
- 3：取 [1,1,1]
- 4：取 [4]
- 5：取 [4,1]
- 6：取 [4,1,1]
- 7：取 [4,1,1,1]
从 0 开始，你可以构造出 8 个连续整数。

示例 3：

输入：nums = [1,4,10,3,1]
输出：20

提示：

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

Submission

运行时间: 95 ms

内存: 20.2 MB

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()
        ans = 1
        for c in coins:
            if c > ans:
                break
            ans += c

        return ans

Explain

题解采用了排序加贪心的算法。首先，将硬币数组排序，这样可以从最小的硬币开始处理。定义变量 `ans` 来记录我们可以连续构造的最大值 +1。遍历排序后的硬币数组，对于每个硬币值 `c`，如果 `c` 小于等于 `ans`（这意味着当前硬币可以用来扩展可构造的连续整数范围），则将其加到 `ans` 中。如果遇到一个硬币值大于 `ans`，则无法用该硬币继续扩展连续范围，循环中断。最后返回 `ans`，这就是从0开始，可以构造出的最大连续整数数量。

时间复杂度: O(n log n)

空间复杂度: O(log n)

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()  # 对硬币进行排序
        ans = 1  # 从可以构造出0开始，因此ans初始化为1
        for c in coins:  # 遍历每个硬币
            if c > ans:  # 如果当前硬币大于当前可以构造的最大连续数+1
                break  # 不能再扩展连续范围，退出循环
            ans += c  # 将当前硬币值加到ans上，扩展连续范围

        return ans  # 返回可以构造出的最大连续数

Explore

在算法中对硬币数组进行排序是为了确保我们能从最小的硬币开始构造连续的整数。这样做可以保证每次添加的硬币都是能够用最小代价扩展当前已构造的连续整数范围的。如果不按顺序来，可能会错过使用较小硬币在某个阶段扩展连续范围的机会。

按照题解的逻辑，如果硬币值c大于当前的ans值，那么意味着在当前的硬币和之前的硬币组合下无法构造出ans这个值，因此这个值及以上的更大值也无法被构造，所以不会漏掉可以构造的连续整数。因此，中断循环是正确的，因为在这一点之后，无法再扩展连续整数范围。

在这个问题中，变量ans表示的是从0开始，可以构造出的连续整数的最大数量加1。因为我们从0开始构造，所以可以直接构造的整数是0，而不需要任何硬币。初始化ans为1意味着我们可以无障碍地开始计数，从0（无需硬币）到ans-1（需要硬币）的整数范围。

按照题解的算法流程，如果硬币数组全部由相同的元素组成，例如coins = [2,2,2,2]，算法将无法正确构造连续整数，因为第一个硬币值2已经大于初始化的ans值1。在这种情况下，算法将直接中断循环，返回1，表示只能构造出整数0。为了处理这种情况，算法需要检查如果第一个硬币值大于1是否有其他方式来填补中间缺失的整数，例如使用其他硬币的组合。然而，在此特例中，所有硬币值相同，无法构造1。因此，对于这种特殊情况，算法无需改变，因为只能构造出整数0。