Medium

题目描述

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

输入: coins = [1,4,10,3,1]
输出: 20

提示:

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

解题思路

这道题的关键在于理解一个贪心的性质：如果我们能够制造出 [0, x-1] 范围内的所有整数，并且有一个硬币价值为 v，那么我们就能制造出 [0, x+v-1] 范围内的所有整数。

核心思路：

  1. 首先将硬币按价值排序，这样可以按照从小到大的顺序处理
  2. 维护一个变量 reach，表示当前能够连续制造的最大值（不包括该值本身）
  3. 对于每个硬币 coin：
    • 如果 coin > reach，说明存在间隙，无法继续扩展连续区间
    • 否则，我们可以将连续区间扩展到 reach + coin

算法步骤：

  1. 对硬币数组排序
  2. 初始化 reach = 1（表示我们能制造 [0, 0]，即只有0）
  3. 遍历排序后的硬币：
    • 如果当前硬币值 ≤ reach，则更新 reach += coin
    • 否则跳出循环
  4. 返回 reach

这个算法的时间复杂度主要来自排序，为 O(n log n)。贪心策略保证了我们总是能找到最优解。

代码实现

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int reach = 1; // 能够制造 [0, reach-1] 的所有值
        
        for (int coin : coins) {
            if (coin > reach) {
                break; // 存在间隙，无法继续
            }
            reach += coin;
        }
        
        return reach;
    }
};

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()
        reach = 1  # 能够制造 [0, reach-1] 的所有值
        
        for coin in coins:
            if coin > reach:
                break  # 存在间隙，无法继续
            reach += coin
        
        return reach

public class Solution {
    public int GetMaximumConsecutive(int[] coins) {
        Array.Sort(coins);
        int reach = 1; // 能够制造 [0, reach-1] 的所有值
        
        foreach (int coin in coins) {
            if (coin > reach) {
                break; // 存在间隙，无法继续
            }
            reach += coin;
        }
        
        return reach;
    }
}

/**
 * @param {number[]} coins
 * @return {number}
 */
var getMaximumConsecutive = function(coins) {
    coins.sort((a, b) => a - b);
    let reach = 1; // 能够制造 [0, reach-1] 的所有值
    
    for (let coin of coins) {
        if (coin > reach) {
            break; // 存在间隙，无法继续
        }
        reach += coin;
    }
    
    return reach;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：排序需要 O(n log n)，遍历数组需要 O(n)，总体为 O(n log n)
  • 空间复杂度：只使用了常数级别的额外空间

相关题目