那么第二步补充数字的话需要补充什么数字呢？如果当前区间是 [1,x]，我们应该添加数字 x + 1，这样可以覆盖的区间为 [1,2*x+1]。如果你选择添加小于 x + 1 的数字，达到的效果肯定没这个区间大。而如果你选择添加大于 x + 1 的数字，那么会导致 x + 1 无法被覆盖。这就是贪心的思想。
关键点解析
维护端点信息，并用前缀和更新区间
代码
代码变量说明：
furthest 表示区间右端点
i 表示当前遍历到的数组索引
ans 是需要返回的答案
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
furthest = i = ans = 0
while furthest < n:
# 可覆盖到，直接用前缀和更新区间
if i < len(nums) and nums[i] <= furthest + 1:
furthest += nums[i] # [1, furthest] -> [1, furthest + nums[i]]
i += 1
else:
# 不可覆盖到，增加一个数 furthest + 1，并用前缀和更新区间
# 如果 nums[i] > furthest + 1，说明我们必须添加一个数 x，其中 1 <= x <= furthest + 1，从贪心的角度我们应该选择 furthest + 1，这在前面已经讲过
furthest = 2 * furthest + 1 # [1, furthest] -> [1, furthest + furthest + 1]
ans += 1
return ans
如果你的区间信息是左闭右开的，代码可以这么写：
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
furthest, i, ans = 1, 0, 0
# 结束条件也要相应改变
while furthest <= n:
if i < len(nums) and nums[i] <= furthest:
furthest += nums[i] # [1, furthest) -> [1, furthest + nums[i])
i += 1
else:
furthest = 2 * furthest # [1, furthest) -> [1, furthest + furthest)
ans += 1
return ans
