8.19 - hard - 68

330. Patching Array

又是一道greedy的题目

class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        patch = 0
        i = 0
        miss = 1
        while miss <= n: #* invariant: [1,miss) is covered */
            if i >= len(nums) or miss < nums[i]:
                miss += miss # patch miss, now we reach miss-1 (already covered) + miss + 1 (next miss)=2*miss
                patch += 1
            else:
                miss += nums[i] # miss >= nums[i], [1,miss) + nums[i] covers miss and move forward
                i += 1

        return patch