330. 按要求补齐数组

题目链接：330. 按要求补齐数组 - 力扣（LeetCode）

 

 

这是一个经典的贪心算法问题，核心思路是维护一个当前能够覆盖的连续整数区间 [1, cover]，通过遍历数组和适时补充数字，最终使 cover达到 n。

算法步骤

1. 初始化 cover = 0（表示能表示 [1, cover]的所有整数），patches = 0（补充数字的个数），指针 i = 0遍历数组。
2. 循环直到 cover >= n：
   • 如果 i未越界且 nums[i] <= cover + 1，则当前数字可以被利用，直接扩展覆盖范围：cover += nums[i]，i++。
   • 否则，说明存在缺口 cover + 1无法表示，必须补充该数字：patches += 1，cover += cover + 1（即添加 cover + 1）。
3. 返回 patches。

正确性证明

贪心策略的关键在于：每次遇到缺口 cover + 1时，补充该数字是最优的。因为补充 cover + 1可以将覆盖范围扩展到 2*cover + 1，且不会遗漏任何更小的数。若补充更大的数，则 cover + 1仍无法被表示；若补充更小的数，则扩展效率更低。因此每次补充当前缺失的最小数字可以保证全局最少补充次数。

复杂度分析

• 时间复杂度：O(m + log n)，其中 m 是数组长度。每个数组元素最多被访问一次，每次补充数字至少使 cover翻倍，故补充次数为 O(log n)。
• 空间复杂度：O(1)。

 

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long stb = 0;
        int m = nums.size();
        int j = 0;
        int ret = 0;
        
        while (stb < n) {
            if (j < m && nums[j] <= stb + 1) stb += nums[j], j++;
            else {
                ret++;
                stb += stb + 1;
            }
        }
        return ret;
    }
};

 

核心特征

1. 连续区间覆盖：问题目标通常是覆盖从1开始的连续整数区间（如 [1, n]），要求区间内每个数都能表示为给定集合中某些元素的和。
2. 集合可扩展：允许向集合中添加数字，要求添加的最少数量。
3. 已排序数组：输入数组往往是已排序的，或者可以排序处理。
4. 子集和表示：关键是用子集和来表示数字，类似于“硬币找零”但要求覆盖所有值。

解题技巧

• 贪心维护覆盖范围：始终维护当前能表示的连续整数范围 [1, cover]，初始 cover=0。
• 缺口填补策略：当遇到无法覆盖的最小数字 miss = cover + 1时，必须添加该数字。这是因为：
  • 如果现有数字中有小于等于 miss的，可以直接利用它扩展覆盖范围。
  • 否则，添加 miss是最优的，因为它能最大程度扩展覆盖范围（cover变为 2*cover+1），且不会遗漏更小的数。
• 遍历与补充结合：遍历数组，若当前数字 num <= cover+1，则将其加入覆盖；否则反复补充 cover+1直到可以容纳 num。

快速判断方法

1. 问题描述关键词：出现“最少补充数字”、“覆盖所有数字”、“子集和表示连续区间”等表述。
2. 数据范围提示：n可能很大（如 2^31-1），暗示需要 O(log n)的贪心策略，而非动态规划。
3. 类似经典问题：这与“硬币找零”中求最少硬币数不同，硬币问题通常针对特定金额，而这里是覆盖区间。
4. 已排序数组：通常输入已排序，提示可以顺序处理。

举一反三

• 变体1：如果要求添加的数字不能重复，算法依然有效，因为添加的数字本身就是新的。
• 变体2：如果数组未排序，先排序再应用此算法。
• 变体3：如果覆盖起点不是1，而是某个值x，可以归一化处理。

掌握这个模式后，遇到类似“连续覆盖”问题，优先考虑贪心维护覆盖区间