My code:
public class Solution {
public int minPatches(int[] nums, int n) {
long max = 0;
int c = 0;
for (int i = 0; max < n;) {
if (i >= nums.length || max < nums[i] - 1) {
max += max + 1;
c++;
}
else {
max += nums[i];
i++;
}
}
return c;
}
}
我觉得这个思想还是很巧妙的。
max 表示的是当前数字下，我能构成的最大数字，并且最小数字和最大数字之间是连续的。
如果 max < nums[i] - 1,
这表示 (max, nums[i]) 这段区域，有些数字我不能表示，就直接跳到了 nums[i]
这里，我就需要 patch 了
但是，我patch的时候，也得注意，用最少的patch，把(preMax, currMax) 连续得连接起来。
那么，我得patch (max + 1) 这个数。
这样的话， [max, max + max + 1] 这段区域内，所有的数字，我都可以表示
然后我一次次得累加，直到 max >= nums[i] - 1
同理， max >= n
Anyway, Good luck, Richardo! -- 10/08/2016
