一、题目
给你一个长度为 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^4 -
1<= coins[i] <=4 * 10^4
三、解题思路
通过题目描述，我们可以找出一下几个关键点：
【关键点1】连续整数是从
0开始的，即：什么也不从coins中取。
【关键点2】可以从coins中拿出任意个硬币，但是不能重复去拿。
【关键点3】假设我们最多构造出了m个连续整数，那么其连续的整数结果集合一定是[0,1,2,3,……,m]。
了解了以上的关键点，我们就来关注一下连续集合的特殊性，即，对于区间[n, m]的连续集合，如果使得集合中每个元素都加x，那么新的集合一定也是连续的，即：[n+x, m+x]。那么根据本题要求，需要[n, m]和[n+x, m+x]这两个集合合并在一起（去重），也一定要具有连续性。那么我们来看下面的图例，大致分为了如下3种情况：
【总结】在情况3种，发生了不连续，即：如果x > m + 1（即：6 > 3 + 1），那么就会产生不连续的情况。而为了方便我们计算，我们可以将题目中给出的coins数组先进行排序操作。那么如果发生了x > m + 1（其中，
x就是coins(i)）的情况，因为是升序排列的，所以后面的元素就不需要对比了。
上面介绍完解题思路后，下面我们还是按照惯例，以一个输入coins为[1,4,10,3,1]为例，模拟一下计算过程。(由于篇幅有限，coins[4]的图例省略没有画）
四、代码实现
class Solution {
public int getMaximumConsecutive(int[] coins) {
Arrays.sort(coins);
int tail = 0; // 连续整数集合的最后一个元素值
for (int coin : coins) {
if (coin > tail + 1) return tail + 1; // 出现断层，直接返回结果
tail += coin; // 更新区间内最大值tail
}
return tail + 1; // 因为从0开始，所以总数为tail加1
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论