题目描述

leetcode1798. 你能构造出连续值的最大数目

给你一个长度为 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

题解——经典贪心题（附上进阶题）

这是一道非常经典的贪心题。330.按要求补齐数组可以视为它的进阶。事实上两题思路基本相同。

思路

本题的思路有种数学归纳法的感觉。需要考虑的就是这样一个问题：

  • 当我们已经可以表示[0,n]时，再给一个整数x，可以表示的整数范围如何变化？

显然，新增的可达数就是把原来的n+1个数都加上x，得到[x,n+x]，新的可以表示的数的范围就是这两部分的并集。在本题中，要求可达域连续，也就是要求x<=n+1，这样可达域就被扩充为[0,n+x]。

初始可达域为{0}，由于x<=n+1的条件限制，我们肯定是从小到大地添加数。我们维护当前可以表示的最大值，也就是上面的n，如果当前最小数满足条件，就添加之，并更新最大值；否则就没有有可以添加的数了，返回答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(),coins.end());//从小到大排序
        int canGet=0;//可以表示的最大值，初始为0
        for(int &num:coins)
            if(num<=canGet+1)//如果当前最小数满足条件，添加并更新
                canGet+=num;
            else//没有可添加的数了，返回
                break;
        return canGet+1;
    }
};

时间复杂度O(NlogN)，主要是排序的复杂度。

进阶题思路

顺便写一下330的题解。这题同样是给出一个序列(已经排好序了)。问的是需要向里面至少添加几个数，才能表示[1,n]的所有数。说白了，就是在无法连起来时，给我们一个补救的机会，那么，该添加什么数呢？同样是贪心的思路，既要求连续，也就是x<=n+1，又希望尽可能扩大可达域，所以就添加n+1好了。细节就不多说了，代码如下：

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long canGet=0,cnt=0,i=0;
        while(canGet<n)
            if(i<nums.size()&&nums[i]<=canGet+1)//满足条件，添加并更新
                canGet+=nums[i++];
            else//添加满足条件的最大数
                canGet+=canGet+1,++cnt;
        return cnt;
    }
};