---

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

• 标签：栈、贪心、数组、动态规划、单调栈
• 难度：困难

题目链接

• 1526. 形成目标数组的子数组最少增加次数 - 力扣

题目大意

描述：给定一个目标数组 $target$。初始数组全为 $0$，长度与 $target$ 相同。每次操作可以将一个连续子数组中的所有元素加 $1$。

要求：返回将初始数组变为 $target$ 所需的最少操作次数。

说明：

• $1 \le target.length \le 10^5$。
• $1 \le target[i] \le 10^5$。

示例：

• 示例 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) 。

解题思路

思路 1：贪心（相邻差分）

1. 核心思想

每次操作选择一个区间 $+1$，等价于在差分视角下：

• 初始数组全 $0$。
• 要使每个位置达到 $target[i]$，需要加的操作总数是 $target[i]$。

关键：从 $target[i-1]$ 到 $target[i]$ 的变化量。如果 $target[i] > target[i-1]$，需要新开始 $target[i] - target[i-1]$ 次操作（即左端点）。如果 $target[i] \le target[i-1]$，则可以利用前面的操作延续。

因此最少操作次数 = $\sum_{i=1}^{n-1} \max(0, target[i] - target[i-1]) + target[0]$。

这个公式的直观理解：每个上升沿需要开启新的操作，下降沿自动结束操作。

2. 具体步骤

第 1 步：初始化 $ans = target[0]$。

第 2 步：遍历 $i = 1 \to n-1$：

• 如果 $target[i] > target[i-1]$，$ans += target[i] - target[i-1]$。

第 3 步：返回 $ans$。

3. 正确性证明

• 差分数组 $diff[0] = target[0]$，$diff[i] = target[i] - target[i-1]$（$i \ge 1$）。
• 每次区间加 $1$ 等价于 $diff[l] += 1$，$diff[r+1] -= 1$。
• 最终每个 $diff[i] > 0$ 都需要一个对应的左端点操作。
• 因此总操作数 = $\sum diff[i]$（只计正数）= $target[0] + \sum_{i=1}^{n-1} \max(0, target[i] - target[i-1])$。

4. 举例说明

以 $target = [1,2,3,2,1]$ 为例：

• $ans = target[0] = 1$。
• $i=1$：$2 > 1$，$ans += 1$，$ans=2$。
• $i=2$：$3 > 2$，$ans += 1$，$ans=3$。
• $i=3$：$2 \le 3$，不变。
• $i=4$：$1 \le 2$，不变。

$ans = 3$。

操作方案：

• $[0,4]$ 加 $1$ → $[1,1,1,1,1]$
• $[1,2]$ 加 $1$ → $[1,2,2,1,1]$
• $[2,2]$ 加 $1$ → $[1,2,3,1,1]$
  等等，还不对。检查：
• $[1,3]$ 加 $1$ → $[1,2,2,1,1]$
• $[2,3]$ 加 $1$ → $[1,2,3,2,1]$

这需要 $1+2=3$ 步（全局 $+1$，然后 $[1,3]$ 加 $1$，$[2,3]$ 加 $1$）。对，是 $3$ 步。

思路 1：代码

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        ans = target[0]
        for i in range(1, len(target)):
            if target[i] > target[i - 1]:
                ans += target[i] - target[i - 1]
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。