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

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

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

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

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