题目描述

给定一个排好序的数组，和一个整数n。 添加补丁数组使得[1,n]这个区间中的任意一个数能由这个数组的和所表达。
问这个补丁数组最小是多大？

样例

nums = [1, 3], n = 6
Return 1.

nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].


nums = [1, 2, 2], n = 5
Return 0.

算法

(贪心) $O(n)$

我们可以维护一个当前能表达的最大范围curcp。
并且维护一个当前数组的最大值curmax，这个最大值可能是我们添加的，也可能是原来数组中的元素。
记录一个patchcount为当前添加的个数。
假设当我们的范围为[1,curcp]的时候。 这个时候如果数组中没有比curcp+1小的数，我们肯定要加一个数进来。
加入的这个数当然要尽可能的大，这样我们的表达范围会变大。 但也要尽可能的小，如果大于curcp+1那么就会有空隙。
所以这时候我们加入curcp+1这个数。
如果数组中有比curcp+1小的数，那么我们就要先用这个数，尽可能先扩充范围。

时间复杂度：扫描了整个数组，所以是$O(n)$

C++ 代码

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patchcount = 0;
        long curmax = 0;
        long curcp = 0;
        int pos = 0;
        while(curcp<n){
            if (pos<nums.size() && curcp+1 >= nums[pos] ){
                curcp += nums[pos++];
                curmax = nums[pos];
            }
            else{
                curmax = curcp+1;
                curcp = curmax + curcp; 
                patchcount++;
            }

        }
        return patchcount;
    }
};