一、核心需求理解

你需要实现 LintCode 3835 题的 minNumberOperation 函数，核心目标是计算将一个初始全为 0 的数组转换为给定 target 数组所需的最少增加次数，每次操作可以对数组中连续的一段元素各加 1。

二、解题思路与代码实现

1. 解题思路分析

这个问题的核心是贪心思想：我们可以把数组的数值变化看作“高度阶梯”，最少操作次数等于所有“上升阶梯”的高度之和。

• 初始数组全为 0，我们从左到右遍历 target 数组；
• 对于每个位置 i，如果 target[i] > target[i-1]（i=0 时，target[-1] 视为 0），则差值 target[i] - target[i-1] 就是需要新增的操作次数；
• 如果 target[i] <= target[i-1]，则无需新增操作（可以复用之前连续区间的操作）。

举个例子：target = [3,1,2,4]

• 第 0 位：3 - 0 = 3 次（操作：[0,0] 加 1 共 3 次）；
• 第 1 位：1 - 3 = -2 → 0 次；
• 第 2 位：2 - 1 = 1 次（操作：[2,2] 加 1 共 1 次）；
• 第 3 位：4 - 2 = 2 次（操作：[3,3] 加 1 共 2 次）；
• 总次数：3+0+1+2 = 6 次（验证：这是最优解）。

2. 完整代码实现

public class Solution {
    /**
     * 计算形成目标数组的最少增加次数
     * @param target 目标数组
     * @return 最少操作次数
     */
    public int minNumberOperation(int[] target) {
        // 边界条件：空数组直接返回 0
        if (target == null || target.length == 0) {
            return 0;
        }
        
        int total = 0;
        // 前一个位置的数值，初始为 0（对应数组前的虚拟位置）
        int prev = 0;
        
        // 遍历目标数组，累加所有上升段的差值
        for (int num : target) {
            if (num > prev) {
                total += num - prev;
            }
            prev = num;
        }
        
        return total;
    }
}

3. 代码关键解释

• 边界处理：先判断数组是否为空，避免空指针异常；
• prev 变量：记录前一个位置的数值，初始为 0（模拟数组第一个元素的“前一个值”）；
• 核心逻辑：遍历每个元素，仅当当前元素大于前一个元素时，累加差值到总次数中；
• 时间复杂度：O(n)（n 为数组长度），仅需一次遍历；
• 空间复杂度：O(1)，仅使用常数级额外空间。

4. 测试用例验证

三、总结

1. 核心思路：最少操作次数等于数组中所有“上升阶梯”的高度之和，利用贪心思想仅累加上升段的差值；
2. 实现关键：通过 prev 变量记录前一个位置的数值，遍历数组时仅计算当前值与前值的正差值；
3. 性能优化：时间复杂度 O(n)、空间复杂度 O(1)，是该问题的最优解法。

这个思路的本质是把“连续区间加 1”的操作，转化为对数组“高度差”的统计，避免了模拟每一次操作（模拟操作会导致时间复杂度升高），是解决这类区间增量问题的经典贪心策略。