给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。
请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
示例 1:
输入:coins = [1,3]
输出:2
解释:你可以得到以下这些值:
输入:coins = [1,1,1,4]
输出:8
解释:你可以得到以下这些值:
输入: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
public int getMaximumConsecutive(int[] coins) {int sum=1;Arrays.sort(coins);for (int coin : coins) {if (sum>=coin){sum+=coin;}}return sum;}
func getMaximumConsecutive(coins []int) int {sum:=1sort.Ints(coins)for _, v := range coins {if sum>=v{sum+=v}}return sum
}