好久没有在平日早上写了
剩我是公司的狗了
945. Minimum Increment to Make Array Unique
思路:
先排列
如果遇到某一区间是nums[j]-nums[i]会小于j-i
就代表这个区间必须透过数个move去撑开成[nums[i], nums[i]+1, nums[i]+2, ...]
若nums[j]-nums[i] >= j-i
代表可以reset 重新开始一个新的区间
def minIncrementForUnique(self, nums: List[int]) -> int:
nums.sort()
start_i, target_diff, ans = 0, 1, 0
for i in range(1,len(nums)):
if (nums[i]-nums[start_i]) < (i-start_i):
ans += (nums[start_i]+target_diff-nums[i])
target_diff += 1
else:
target_diff = 1
start_i = i