题目描述

给你一个长度为 n 的整数数组 coins，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i]。如果你从这些硬币中选出一部分硬币，它们的和为 x，那么称，你可以 构造 出 x。

请返回从 0 开始（包括 0），你最多能 构造 出多少个连续整数。

你可能有多个相同值的硬币。

样例

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 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 个连续整数。

输入：nums = [1,4,10,3,1]
输出：20

限制

• coins.length == n
• 1 <= n <= 4 * 10^4
• 1 <= coins[i] <= 4 * 10^4

算法

(排序) $O(n \log n)$

1. 将所有硬币的面值从小到大排序。
2. 设置一个变量 ma，表示当前可以组成 0 到 ma 面值的所有硬币。
3. 初始时，ma = 0，然后开始遍历数组。遍历时，如果发现 coins[i] > ma + 1，则说明 ma + 1 这个值无论如何都无法构成，返回答案 ma + 1。
4. 否则，ma 可以更新为 ma + coins[i]。

时间复杂度

• 排序后遍历数组一次，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        const int n = coins.size();
        sort(coins.begin(), coins.end());

        int ma = 0;
        for (int i = 0; i < n; i++) {
            if (coins[i] > ma + 1)
                return ma + 1;
            ma += coins[i];
        }

        return ma + 1;
    }
};