好久沒有在平日早上寫了
剩我是公司的狗了
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