Question

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

解法

方法一：排序 + 贪心

我们先对数组进行排序。然后定义 $ans$ 表示当前能够构造的连续整数的个数，初始化为 $1$。

遍历数组，对于当前遍历到的元素 $v$，如果 $v \gt ans$，说明无法构造出 $ans+1$ 个连续的整数，因此直接跳出循环，返回 $ans$ 即可。否则，说明可以构造出 $ans+v$ 个连续的整数，因此更新 $ans$ 为 $ans+v$。

最后返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组的长度。

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

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

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

func getMaximumConsecutive(coins []int) int {
  sort.Ints(coins)
  ans := 1
  for _, v := range coins {
    if v > ans {
      break
    }
    ans += v
  }
  return ans
}

function getMaximumConsecutive(coins: number[]): number {
  coins.sort((a, b) => a - b);
  let ans = 1;
  for (const v of coins) {
    if (v > ans) {
      break;
    }
    ans += v;
  }
  return ans;
}