lc-1526-minimum-number-of-increments-on-subarrays-to-form-a-target-array.org

LC 1526. 形成目标数组的子数组最少增加次数

https://leetcode-cn.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

关于使用差分数组来解决此题：

• Solution1
• Solution2

这题非常巧妙的是使用差分数组来简化区间操作：

• 数组 `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