class Solution {
public:
int getMaximumConsecutive(vector<int>& coins) {
}
};
1798. 你能构造出连续值的最大数目
给你一个长度为 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 == n1 <= n <= 4 * 1041 <= coins[i] <= 4 * 104原站题解
javascript 解法, 执行用时: 164 ms, 内存消耗: 50.3 MB, 提交时间: 2023-02-04 15:07:44
/**
* @param {number[]} coins
* @return {number}
*/
var getMaximumConsecutive = function(coins) {
coins.sort((a, b) => a - b);
var r = 1;
for(var i = 0; i < coins.length; ++i) {
if(coins[i] > r) { break; }
r += coins[i];
}
return r;
};
java 解法, 执行用时: 18 ms, 内存消耗: 49.2 MB, 提交时间: 2023-02-04 15:07:09
class Solution {
public int getMaximumConsecutive(int[] coins) {
Arrays.sort(coins);
int r = 1;
for(int coin : coins) {
if(coin > r) { break; }
r += coin;
}
return r;
}
}
golang 解法, 执行用时: 112 ms, 内存消耗: 7 MB, 提交时间: 2023-02-04 15:06:26
func getMaximumConsecutive(coins []int) int {
sort.Ints(coins)
r := 1
for _, coin := range coins {
if coin > r {
break
}
r += coin
}
return r
}
cpp 解法, 执行用时: 104 ms, 内存消耗: 65 MB, 提交时间: 2022-12-11 12:17:16
class Solution {
public:
int getMaximumConsecutive(vector<int>& coins) {
sort(coins.begin(), coins.end());
int x = 0;
for (int y: coins) {
if (y > x + 1) {
break;
}
x += y;
}
return x + 1;
}
};
python3 解法, 执行用时: 124 ms, 内存消耗: 19.1 MB, 提交时间: 2022-12-11 12:16:59
'''
由于我们需要从 0 开始构造出尽可能多的连续整数，而不在区间 [0,x] 中的最小整数是 x+1，
因此如果 x+1 在区间 [y,y+x] 中，那么元素 y 就会使得构造出的连续整数的范围从 [0,x] 增加到 [0,y+x]；
否则，元素 y 不会对答案产生任何影响。
由于数组中的元素都是正整数，那么 x+1≤y+x 恒成立，我们只需要求 y≤x+1 即可保证 x+1 在区间 [y,y+x] 中。
'''
class Solution:
def getMaximumConsecutive(self, coins: List[int]) -> int:
coins.sort()
x = 0
for y in coins:
if y > x + 1:
break
x += y
return x + 1