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

Difficulty
Hard
Tags
差分
动态规划
单调栈
URL
https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
Star
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
  • 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：
输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
示例 2：
输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：
输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：
输入：target = [1,1,1,1]
输出：1
提示：
  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5
通过次数3,954提交次数6,220

法 1 差分

思路
initial 要和 target 相同 转化为
initial 的差分 和 target 相同
为什么能想到差分呢？
因为差分是最好表达一段区间的相加操作的。转化为差分后，只需要计算差分数组中 正数的和 就是最后需要操作的次数。
题解
class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        cha_fen = [0 for _ in target]
        cha_fen[0] = target[0]
        
        for i in range(1, len(target)):
            cha_fen[i] = target[i] - target[i-1]

        res = 0
        for i in range(0, len(cha_fen)):
            res += cha_fen[i] if cha_fen[i] > 0 else 0

        return res

动态规划

思路
当下一个数小于前一个时，dp不变；大于时，需要额外加入差值表示的次数
dp[i] = dp[i-1] if target[i] <= target[i-1]
dp[i] = dp[i-1] + target[i] - target[i-1] if target[i] > target[i-1]
有点「单调栈」的思想，考虑每个元素左侧相邻元素的贡献值。
题解
class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        dp = [0 for _ in range(len(target))]
        dp[0] = target[0]
        for i in range(1, len(target)):
            if target[i] <= target[i-1]:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + target[i] - target[i-1]
        return dp[-1]