[每日一题]1798.你能构造出连续值的最大数目
1798. 你能构造出连续值的最大数目 给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以 构造 出 x 。
请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
输入：coins = [1,3] 输出：2 解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1] 从 0 开始，你可以构造出 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 个连续整数。
Solution
class Solution {
public int getMaximumConsecutive(int[] coins) {
int n = coins.length;
Arrays.sort(coins);
if (coins[0] != 1) return 1;
int res = 1;
for (int i = 1; i < n; i++) {
//coins[i-1]前面所有元素组合的res能够覆盖coins[i]和coins[i-1]之间的gap
//i-1之前所有元素的组合是0到res-coins[i-1]，gap记作coins[i]-coins[i-1]-1
//例如：[1,1,3,4,10]的gap分别为-1,1,0,5，
if (res-coins[i-1] >= coins[i]-coins[i-1]-1) {
res += coins[i];
}
//否则无法覆盖gap
else break;
}
return res+1;
}
}