0330. Patching Array ==================== 题目信息 -------- :题号: 0330 :难度: Hard :主题: 升序正整数数组、子集和覆盖、添加元素、最少数量 :原题: `LeetCode 0330 `_ :重点: 每个数组元素至多使用一次、覆盖闭区间 ``[1,n]``、允许添加正整数、返回最少补丁数 题目重述 -------- 给定按升序排列的正整数数组 ``nums`` 和正整数 ``n``。可以向数组中添加若干个正整数;添加完成后,要求对 ``[1, n]`` 中的每个整数,都能从最终数组中选取某些元素并用它们的和表示出来。 每个数组位置在一次求和中至多选用一次,数组中的重复值视为不同位置。返回满足完整覆盖要求所需添加元素的最少数量。``nums`` 的长度位于 ``[1, 1000]``,元素位于 ``[1, 10^4]``,``n`` 位于 ``[1, 2^31-1]``。 自建示例 -------- 只存在一个覆盖缺口: .. code-block:: text 输入:nums = [1, 2, 8],n = 15 输出:1 解释:原数组能表示 1 至 3;补入 4 后能表示 1 至 7,再结合 8 即可表示 1 至 15,所以只需一个补丁。 已有数组已经完整覆盖: .. code-block:: text 输入:nums = [1, 2, 4],n = 7 输出:0 解释:通过选择这些元素的不同子集,可以表示 1 到 7 的每个整数,不需要添加新值。 维护当前连续覆盖的右端 ------------------------ 设 ``reach`` 表示当前元素可以覆盖的连续区间为 ``[1, reach - 1]``,初始没有元素,所以 ``reach = 1``。若下一个未处理的原数组元素 ``nums[i] <= reach``,它可以和已有子集组合,把覆盖右端扩展到 ``reach + nums[i] - 1``,因此令 ``reach += nums[i]``。 如果 ``nums[i] > reach``,金额 ``reach`` 无法由已有元素表示,而任何更大的补丁也不能表示这个缺口;最小且最有用的选择只能是补入 ``reach``。加入它后,原来 ``[1, reach - 1]`` 的所有数与补丁组合,恰好连续覆盖到 ``2 * reach - 1``,所以令 ``reach += reach``。只要 ``reach <= n`` 就必须继续补齐或吸收原数组元素。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int minPatches(std::vector& nums, int n) { long long reach = 1; int index = 0; int patches = 0; while (reach <= n) { if (index < static_cast(nums.size()) && nums[index] <= reach) { reach += nums[index++]; } else { reach += reach; ++patches; } } return patches; } }; 代码分析 -------- 数组已升序排列,所以一旦当前元素大于缺口,后面的原元素也不可能先填补它;补入 ``reach`` 是在该时刻能把连续覆盖区间扩展得最远的最优选择。使用 ``long long`` 是因为覆盖端点会超过 ``n`` 才停止,而 ``n`` 接近 32 位上界。每个原数组元素最多处理一次,时间复杂度为 ``O(nums.size())``,额外空间为 ``O(1)``。