按要求补齐数组如何用贪心覆盖区间？miss 变量代表什么？

简化版

补齐数组用 miss 表示当前最小无法覆盖的正整数，也就是已经能覆盖 [1, miss)。如果数组当前数字 nums[i] <= miss，就能把覆盖范围扩展到 [1, miss + nums[i])；否则必须补一个 miss，这是扩展范围最大的最优补丁。

详细版

初始化 miss=1，表示一开始什么都覆盖不了。遍历有序数组：若当前数不超过 miss，它可以和已有覆盖区间组合，使覆盖上界增加 nums[i]；若当前数大于 miss，说明 miss 这个数无法由现有数字组成，只能补一个数。补 miss 可以把覆盖从 [1, miss) 扩展到 [1, 2*miss)。

循环直到 miss > n。时间复杂度 O(m)，其中 m 是数组长度加补丁次数；空间复杂度 O(1)。关键是理解覆盖区间不变量。

完整版教学

一、miss 到底表示什么

miss 表示当前最小还不能组成的正整数。换句话说，使用已经处理过的数字，我们可以覆盖：

[1, miss)

如果 miss=8，意思是 1 到 7 都能组成，但 8 还不能确定能组成。

记忆钩子：miss 不是漏掉的补丁值那么简单，它是“当前覆盖边界”。

这个不变量是整题的钥匙。

二、为什么 nums[i] <= miss 可以扩展覆盖

假设当前已经能覆盖 [1, miss)，也就是 1..miss-1。如果新数字 x <= miss，那么用 x 加上旧覆盖范围，可以得到：

x
x + 1
x + 2
...
x + (miss - 1)

因为 x <= miss，新范围会和旧范围无缝衔接，覆盖扩展到：

[1, miss + x)

例如已覆盖 [1,8)，来了 x=5，新覆盖可到 [1,13)。

三、为什么 nums[i] > miss 时必须补

如果当前数组数字 x > miss，那么所有未处理数字都至少大于 x，更不可能组成 miss。旧数字最多覆盖到 miss-1，新数字又太大，中间断了。

已覆盖：1..7
当前数字：10
数字 8 无法组成

所以必须补一个不超过 miss 的数，否则 miss 依然无法被覆盖。

四、为什么补 miss 最优

当必须补数时，补的数不能超过 miss，否则仍然覆盖不了 miss。在所有可补的数中，补 miss 最大，能把覆盖范围扩展得最远。

补丁值	新覆盖上界
补 1	`miss + 1`
补 `miss-1`	`2*miss - 1`
补 `miss`	`2*miss`

所以补 miss 是局部最优，也不会伤害全局。

五、代码模板

int minPatches(int[] nums, int n) {
    long miss = 1;
    int i = 0, patches = 0;
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) {
            miss += nums[i];
            i++;
        } else {
            miss += miss;
            patches++;
        }
    }
    return patches;
}

miss 要用 long，因为 miss += miss 可能超过 int 范围。循环条件是 miss <= n，一旦 miss > n，说明 1..n 已经全部覆盖。

六、用例子推演

nums=[1,5,10]，n=20：

miss=1，nums[0]=1 <=1，覆盖到 [1,2)
miss=2，nums[1]=5 >2，补 2，覆盖到 [1,4)
miss=4，nums[1]=5 >4，补 4，覆盖到 [1,8)
miss=8，nums[1]=5 <=8，覆盖到 [1,13)
miss=13，nums[2]=10 <=13，覆盖到 [1,23)

miss=23 > 20，答案是补 2 个数：2 和 4。

七、常见误区与追问

误区：miss 表示当前已经覆盖的最大值。 更准确说，已覆盖 [1, miss)，miss 是最小未覆盖值。
误区：数组当前数大于 miss 时继续跳过。 跳过无法解决缺口，必须补丁。
误区：补一个比 miss 大的数。 这样仍然覆盖不了 miss，不合法。
追问：为什么补 miss 扩展最大？ 在不超过 miss 的合法补丁中，miss 最大，新覆盖上界最大。
追问：为什么 nums 要有序？ 覆盖推导依赖后续数字不小于当前数字；无序要先排序。
追问：为什么用 long？ 覆盖边界可能翻倍超过 int。

八、加强记忆

补齐数组的核心是覆盖区间 [1, miss)。来了一个不超过 miss 的数，就能把覆盖右边界往前推；来了一个大于 miss 的数，中间断档，必须补。补丁选 miss，因为它既刚好补上缺口，又让覆盖翻倍。这个题会了 miss 不变量，就不需要硬背。

简化版

详细版