按要求补齐数组 图解题解

这道题到底在问什么

nums

[1,5,10]

n

20

输出

2

含义

补 2、4 后即可覆盖 1~20

最优解：一步一步想明白

1. 3全题就靠一个数 miss:它表示「1 到 miss−1 我都能凑出来,miss 是第一个缺口」。一开始 miss=1,意思是「啥都还没覆盖」。我们要做的就是想办法把 miss 一路推过 n。
2. 4关键的两条规矩:能覆盖 [1,miss) 时,再来个 x ≤ miss,新范围 [1, miss+x) 中间不会断;但 x > miss 时,miss 自己就卡死了。补数时补谁最赚?补 miss 本身——它能把覆盖范围一口气翻倍到 [1, 2·miss)。
3. 5覆盖 [1,1) = 空,指针 i 看 nums[0]目标 n = 20。指针 i 指向 nums[0]=1。miss=1 表示现在连 1 都凑不出。问:手头的 nums[0]=1 能帮上忙吗?
4. 6用掉 1,miss 接到 21 ≤ miss(1),免费拿来用!覆盖范围接上,miss 从 1 长到 2——现在能凑出 1 了。这格变绿表示已用上,指针准备右移。
5. 7封存 nums[0],看 nums[1]=5nums[0] 用完封存变灰,指针 i 挪到 nums[1]=5。现在第一个凑不出的数是 2。看看 5 能不能接上去。
6. 85 和 miss 摆一起比大小每一轮都做同一个判断:指针指的数和 miss 谁大?这里 nums[1]=5 比 miss=2 大,意味着 5 暂时接不上当前的覆盖范围。
7. 95 太大,2 凑不出 → 必须补5 > miss(2)!若直接用 5,覆盖会从「能凑 1」跳到 5,中间 2、3、4 全断了。所以不能用 5,得先补一个数把缺口 2 堵上。
8. 10补 2,覆盖翻倍 → [1,4)补谁最划算?补 miss 自己 = 2!原来能凑 [1,2),加进一个 2 后,2、3(=1+2)也能凑了 → 覆盖一口气翻倍到 [1,4)。miss 从 2 跳到 4,补丁计数 +1。
9. 11缺口 4 仍在 → 再补补完一个 2 后再看:nums[1] 还是 5,5 > miss(4),缺口变成了 4。5 还是接不上,只能再补一次。
10. 12补 4,覆盖翻倍 → [1,8)同样的招:补 miss=4,覆盖再翻倍到 [1,8)——现在 1~7 全能凑。miss 从 4 跳到 8,补丁计数到 2。这就是答案里的两个补丁:2 和 4。
11. 13翻倍两次后再看 5miss 翻倍两次到 8 之后再做同样的比较:nums[1]=5 这次 ≤ miss(8) 了!说明 5 现在能无缝接到覆盖范围上,不用再补。
12. 14用掉 5,miss 接到 135 ≤ miss(8) 成立,免费拿来用!覆盖从 [1,8) 扩到 [1,13),miss 跳到 13。nums[1] 变绿,指针准备移向最后一个数。
13. 15封存 nums[1],看 nums[2]=10nums[1] 用完封存,指针 i 挪到最后的 nums[2]=10。现在第一个缺口是 13。看 10 能不能接上。
14. 16最后一个数和 miss 比最后一个数 nums[2]=10 和 miss=13 比:10 ≤ 13,又能无缝接上,不用补。
15. 17用掉 10,miss 接到 2310 ≤ miss(13),拿!覆盖从 [1,13) 扩到 [1,23),miss 一举冲到 23。注意 23 已经超过 n=20 了。
16. 18覆盖已盖住 1~20,答案 = 2miss 已经 > n=20,说明 1~20 全覆盖到了,循环结束。整个过程只补了 两个数(2 和 4)——这就是最少补丁数 2。三个原数(绿色)都派上了用场。
17. 19贪心为什么对?因为补 miss 让覆盖范围增长最快(翻倍)——补任何比 miss 小的数都不如它,补比 miss 大的数又会留缝。所以每次补 miss 是局部最优也是全局最优。
18. 20开局 miss=1,指针看 nums[0]=1换组数据 nums=[1,3], n=6 再走一遍,体会「拿原数」和「补缺口」如何交替。开局 miss=1,指针指向 nums[0]=1。
19. 21用掉 1,miss → 21 ≤ miss,拿来用,miss 长到 2。nums[0] 变绿。
20. 22补 miss=2,翻倍 → [1,4)指针到 nums[1]=3,3 > miss(2),缺口 2 卡住了。补 miss=2,覆盖翻倍到 [1,4),miss 跳到 4,补丁计数 1。
21. 23用掉 3,miss → 7miss 涨到 4 后 3 ≤ miss(4),拿!覆盖扩到 [1,7),miss 跳到 7。nums[1] 变绿。
22. 24[1,7) 盖住 1~6miss=7 已 > n=6,1~6 全覆盖。这例只补了 1 个数(就是 2),答案 1。
23. 28覆盖 [1,2),来了个 5已覆盖 [1,2)、缺口是 2 时:补 2 直接翻倍到 [1,4) 最划算;补 3 连缺口 2 都没堵上;补 5 会让 2、3、4 都断掉。所以只能补 miss 自己。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def minPatches(self, nums, n):
        patches = 0
        i = 0
        miss = 1                       # 第一个还凑不出的数
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]        # 免费拿原数, 接上覆盖
                i += 1
            else:
                miss += miss           # 补 miss, 覆盖翻倍
                patches += 1
        return patches

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patches = 0, i = 0;
        long long miss = 1;            // 用 long long 防溢出
        while (miss <= n) {
            if (i < (int)nums.size() && nums[i] <= miss) {
                miss += nums[i];
                i++;
            } else {
                miss += miss;          // 翻倍
                patches++;
            }
        }
        return patches;
    }
};

class Solution {
    public int minPatches(int[] nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;                 // 用 long 防溢出
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i];
                i++;
            } else {
                miss += miss;          // 翻倍
                patches++;
            }
        }
        return patches;
    }
}

复杂度

面试官可能追问