README.md

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

English Version

题目描述

给你一个长度为 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 * 104
• 1 <= coins[i] <= 4 * 104

解法

先对 coins 数组进行排序。

假设前 i 个数所有构造的的连续整数的个数为 res，初始化为 1。

遍历排序后的 coins 数组：

• 若 coins[i] > res，说明接下来无法组成 res + 1 个连续整数，跳出循环。

  对于 1, 3，若遍历到 3，此时前面的连续整数个数为 2，即连续整数为：0, 1。此时 3 大于 2，无法构成连续整数 0, 1, 2，所以最大连续整数个数为 2。

• 若 coins[i] <= res，说明有 coins[i] 个数也能构成连续整数。

Python3

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        res = 1
        for coin in sorted(coins):
            if coin > res:
                break
            res += coin
        return res

Java

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        int res = 1;
        Arrays.sort(coins);
        for (int coin : coins) {
            if (coin > res) {
                break;
            }
            res += coin;
        }
        return res;
    }
}

...