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