按要求补齐数组

全题就靠一个数 miss:它表示「1 到 miss−1 我都能凑出来,miss 是第一个缺口」。一开始 miss=1,意思是「啥都还没覆盖」。我们要做的就是想办法把 miss 一路推过 n。

关键的两条规矩:能覆盖 [1,miss) 时,再来个 x ≤ miss,新范围 [1, miss+x) 中间不会断;但 x > miss 时,miss 自己就卡死了。补数时补谁最赚?补 miss 本身——它能把覆盖范围一口气翻倍到 [1, 2·miss)。

开局 · miss = 1：目标 n = 20。指针 i 指向 nums[0]=1。miss=1 表示现在连 1 都凑不出。问:手头的 nums[0]=1 能帮上忙吗?

nums[0]=1 ≤ miss=1 · 拿!：1 ≤ miss(1),免费拿来用!覆盖范围接上,miss 从 1 长到 2——现在能凑出 1 了。这格变绿表示已用上,指针准备右移。

指针 → nums[1]：nums[0] 用完封存变灰,指针 i 挪到 nums[1]=5。现在第一个凑不出的数是 2。看看 5 能不能接上去。

比一比 · nums[1]=5 vs miss=2：每一轮都做同一个判断:指针指的数和 miss 谁大?这里 nums[1]=5 比 miss=2 大,意味着 5 暂时接不上当前的覆盖范围。

nums[1]=5 > miss=2 · 出现缺口!：5 > miss(2)!若直接用 5,覆盖会从「能凑 1」跳到 5,中间 2、3、4 全断了。所以不能用 5,得先补一个数把缺口 2 堵上。

补丁① · 补 miss=2：补谁最划算?补 miss 自己 = 2!原来能凑 [1,2),加进一个 2 后,2、3(=1+2)也能凑了 → 覆盖一口气翻倍到 [1,4)。miss 从 2 跳到 4,补丁计数 +1。

nums[1]=5 还是 > miss=4：补完一个 2 后再看:nums[1] 还是 5,5 > miss(4),缺口变成了 4。5 还是接不上,只能再补一次。

补丁② · 补 miss=4：同样的招:补 miss=4,覆盖再翻倍到 [1,8)——现在 1~7 全能凑。miss 从 4 跳到 8,补丁计数到 2。这就是答案里的两个补丁:2 和 4。

再比一比 · nums[1]=5 vs miss=8：miss 翻倍两次到 8 之后再做同样的比较:nums[1]=5 这次 ≤ miss(8) 了!说明 5 现在能无缝接到覆盖范围上,不用再补。

nums[1]=5 ≤ miss=8 · 终于能拿!：5 ≤ miss(8) 成立,免费拿来用!覆盖从 [1,8) 扩到 [1,13),miss 跳到 13。nums[1] 变绿,指针准备移向最后一个数。

指针 → nums[2]：nums[1] 用完封存,指针 i 挪到最后的 nums[2]=10。现在第一个缺口是 13。看 10 能不能接上。

比一比 · nums[2]=10 vs miss=13：最后一个数 nums[2]=10 和 miss=13 比:10 ≤ 13,又能无缝接上,不用补。

nums[2]=10 ≤ miss=13 · 拿!：10 ≤ miss(13),拿!覆盖从 [1,13) 扩到 [1,23),miss 一举冲到 23。注意 23 已经超过 n=20 了。

miss=23 > n=20 · 收工!：miss 已经 > n=20,说明 1~20 全覆盖到了,循环结束。整个过程只补了 两个数(2 和 4)——这就是最少补丁数 2。三个原数(绿色)都派上了用场。

贪心为什么对?因为补 miss 让覆盖范围增长最快(翻倍)——补任何比 miss 小的数都不如它,补比 miss 大的数又会留缝。所以每次补 miss 是局部最优也是全局最优。

再看一例 · nums=[1,3], n=6：换组数据 nums=[1,3], n=6 再走一遍,体会「拿原数」和「补缺口」如何交替。开局 miss=1,指针指向 nums[0]=1。

nums[0]=1 ≤ miss=1 · 拿!：1 ≤ miss,拿来用,miss 长到 2。nums[0] 变绿。

nums[1]=3 > miss=2 · 缺口!补 2：指针到 nums[1]=3,3 > miss(2),缺口 2 卡住了。补 miss=2,覆盖翻倍到 [1,4),miss 跳到 4,补丁计数 1。

nums[1]=3 ≤ miss=4 · 拿!：miss 涨到 4 后 3 ≤ miss(4),拿!覆盖扩到 [1,7),miss 跳到 7。nums[1] 变绿。

miss=7 > n=6 · 收工!答案 = 1：miss=7 已 > n=6,1~6 全覆盖。这例只补了 1 个数(就是 2),答案 1。

雷区实演 · 缺口该补谁：已覆盖 [1,2)、缺口是 2 时:补 2 直接翻倍到 [1,4) 最划算;补 3 连缺口 2 都没堵上;补 5 会让 2、3、4 都断掉。所以只能补 miss 自己。

边界三连：先想空数组(纯翻倍)、刚好够用(补 0)、n 极大(防溢出)三种,代码就稳了。

面试追问：把「补 miss 为何最优」「为何用 long」「O(m+log n)」讲清楚,是这题面试的得分点。