题目

给你一个整数数组 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

解题思路

解题的关键在于将问题进行转化。

我们不考虑“每次操作选择一个子数组”这个过程，而是从左到右遍历 target 数组，只关注相邻两个元素的变化。

我们可以把 target 数组想象成一个“山脉”的轮廓。我们的目标是用最少的“水平”操作（每次操作都是一个水平的“+1”条）来“搭建”起这个山脉。

详细思路分解

考虑第一个元素 target[0]
- initial 数组是 [0, 0, 0, ...]。
- 为了让 initial[0] 达到 target[0]，我们至少需要 target[0] 次操作。
- 这些操作_必须_包含 index 0。
- 贪心选择：我们假设这 target[0] 次操作都尽可能向右延伸，覆盖了所有元素。
- 此时，我们付出的基础成本是 ans = target[0]。
考虑第二个元素 target[1]
- 我们从左到右看，target[0] 的 target[0] 次操作已经“顺便”让 target[1] 也增加了 target[0] 次。
- 情况 A：target[1] <= target[0] （例如：[3, 1, ...]）
  - target[1] 需要 1，但它已经被“顺便”操作了 3 次。
  - 这意味着，为了满足 target[0] 所需的 3 次操作，已经_完全足够_满足 target[1] 的需求了。
  - 我们不需要为 target[1] 支付任何_新_的成本。
- 情况 B：target[1] > target[0] （例如：[1, 2, ...]）
  - target[1] 需要 2，但它只被“顺便”操作了 1 次（来自 target[0] 的基础成本）。
  - 它还差 target[1] - target[0] 次操作（即 2 - 1 = 1 次）。
  - 这 1 次新操作_必须_从 index 1 开始（或之前），但它_不能_在 index 0 上执行（因为 target[0] 已经满足了）。
  - 因此，我们_必须_增加 target[1] - target[0] 次新的操作。
  - ans += target[1] - target[0]。
推广到 target[i]
- 当我们遍历到 target[i] 时，我们假设它已经被 target[i-1] 所需的操作“顺便”操作了 target[i-1] 次。
  - （注：这只是一个思考模型。更严谨地说是：为了满足 target[i-1]，我们所累计的操作中，有 target[i-1] 次是覆盖了 index i-1 的，我们可以让这些操作_同样_覆盖 index i。）
- 如果 target[i] <= target[i-1]（山脉在“下坡”或“平走”，例如 [3, 2, 1]）
  - target[i-1] 所需的操作已经_足够_满足 target[i]。
  - 不需要任何新操作，ans 不增加。
- 如果 target[i] > target[i-1]（山脉在“上坡”，例如 [1, 2, 3]）
  - target[i-1] 的操作只提供了 target[i-1] 的高度。
  - 我们还差 target[i] - target[i-1] 的高度。
  - 这部分_差值_代表了必须开始的_新_操作。
  - ans += target[i] - target[i-1]。

具体代码

func minNumberOperations(target []int) int {

    ans := target[0]
    for i := 1; i < len(target); i++ {
        if target[i] > target[i - 1] {
            ans += target[i] - target[i - 1]
        }
    }
    return ans
    
}

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

beautifulremi

题目

解题思路

详细思路分解

具体代码