LC1798. 你能构造出连续值的最大数目(JAVA)

题目描述

难度 - 中等
Leetcode - 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 == n
1 <= n <= 4 * 10^4
1 <= coins[i] <= 4 * 10^4
1
2
3

贪心算法

这道题呢，我们可以理解为前缀和数组有多少是连续的，如果直接算前缀和，然后再排序，时间上肯定无法满足，
因为要用贪心，因为是凑硬币，所以顺序不影响结果，我们先把数组排好序，
然后在遍历时，求出前缀和，后面的数字如果大于前缀和 加一，那么肯无法构成连续的了，就可以中断遍历了。
如果满足，我们就计算下去，求出最大的前缀和，比如最大的连续前缀和是7，那么从0开始，肯定就能有8个答案，

代码演示

class Solution {
    public int getMaximumConsecutive(int[] coins) {
       Arrays.sort(coins);
       int ans = 0;
       for(int x : coins){
           if(x > ans + 1){
               break;
           }
           ans += x;
       }
       return ans + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13