2952.需要添加的硬币的最小数量

链接：2952.需要添加的硬币的最小数量
难度：Medium
标签：贪心、数组、排序
简介：请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。

题解 1 - python

• 编辑时间：2024-03-31
• 执行用时：109ms
• 内存消耗：27.09MB
• 编程语言：python
• 解法介绍：记录当前所能表示的区间内，再依次增加数据。

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        ans = 0
        idx = 0
        end = 1 # [0, end - 1]
        while end - 1 < target:
            if idx < len(coins) and coins[idx] <= end:
                end += coins[idx]
                idx += 1
            else:
                end += end
                ans += 1
        return ans