1798. 你能构造出连续值的最大数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个长度为 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
# 思路
对数组进行排序，如果前面已经构造出最大连续值为 x，遍历数组，若当前值为 y 且 x + 1 >= y， 则可以构造出 [0, x + y]，总数为 x + y + 1
# 解法
class Solution {
public int getMaximumConsecutive(int[] coins) {
// 把 x 加 1 ，最终答案变为 x + y
int x = 1;
Arrays.sort(coins);
for (int y : coins) if (x >= y) x = x + y;
return x;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 总结
- 分析出几种情况，然后分别对各个情况实现
