1526. 形成目标数组的子数组最少增加次数
https://leetcode-cn.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
关于使用差分数组来解决此题:
这题非常巧妙的是使用差分数组来简化区间操作:
- 数组
nums[0..n-1]
的差分组可以定位为nums[0], nums[1]-nums[0] .. nums[n-1]-nums[n-2]
- 如果我们要在某个区间内
nums[L..R] + 1
的话,那么对应到差分数组上我们只需要nums[L] + 1, nums[R+1]-1
, 这个操作是一一对应的 - 然后
initial
数组它对应的差分数组其实就是[0,0,0...]
, 我们的目的就是要将它变为target
的差分数组 - 因为
target[i]>0
所以差分数组的和肯定是大于0的,所以我们只需要关心有多少个nums[L]+1
这样的操作 - 其实在这个算法基础上,我们也不难求解出应该如何操作:维护两个指针,他们的值分别是>0和<0的,不断地找到
nums[L..R]
这样的区间
class Solution: def minNumberOperations(self, target: List[int]) -> int: n = len(target) diff = target.copy() for i in range(1, n): diff[i] = target[i] - target[i - 1] ans = 0 for i in range(n): if diff[i] > 0: ans += diff[i] debug = False if debug: ops = [] t = 0 while t < n: if diff[t] < 0: break t += 1 for i in range(n): while diff[i] > 0: diff[i] -= 1 while t < n and diff[t] >= 0: t += 1 if t < n: diff[t] += 1 ops.append((i, t - 1)) # print(ans, ops) assert len(ops) == ans return ans