LeetCode 每日一题笔记

0. 前言

• 日期：2025.10.30
• 题目：1526. 形成目标数组的子数组最少增加次数
• 难度：困难
• 标签: 贪心算法、数组

1. 题目理解

问题描述：
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。

请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 在 initial 中选择 任意子数组，并将子数组中每个元素增加 1 。

• 答案保证在 32 位有符号整数以内。

示例：

输入：target = [1,2,3,2,1] 输出：3 解释：我们需要至少 3 次操作从 initial 数组得到 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. 解题思路

核心观察

每次操作是对一个子数组整体加1，可以将 target 数组理解为“多层叠加的结构”。最少操作次数等于**“基础层”次数加上“额外层”次数**：

• 基础层：由第一个元素的数值决定（需要 target[0] 次操作来构建最底层）。
• 额外层：对于第 i 个元素（i ≥ 1），如果 target[i] > target[i-1]，则差值 target[i] - target[i-1] 就是需要额外增加的操作次数（因为前一个元素的“高度”已被覆盖，当前元素需要额外的子数组操作来弥补差值）。

算法步骤

1. 特殊情况处理：若数组为空，直接返回 0。
2. 初始化结果 res 为 target[0]（基础层操作次数）。
3. 从第二个元素开始遍历数组，若当前元素 target[i] 大于前一个元素 target[i-1]，则将差值 target[i] - target[i-1] 加到 res 中。
4. 遍历结束后，res 即为最少操作次数。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public int minNumberOperations(int[] target) {
         int res=0;
         res+=target[0];
         for(int i=1;i<target.length;i++){
            int temp=(target[i]-target[i-1]>0)?target[i]-target[i-1]:0;
            res+=temp;
         }
         return res;
    }
}

4. 代码优化说明

该算法的时间复杂度为 ( O(n) )（n 是数组长度），空间复杂度为 ( O(1) )，已经是最优解，无需额外优化。

5. 复杂度分析

• 时间复杂度：( O(n) )，仅需遍历一次数组。
• 空间复杂度：( O(1) )，仅需常数级额外空间。

6. 总结

本题的核心思路是**“层叠高度差分析”**，通过观察相邻元素的差值来计算最少操作次数，属于贪心算法的典型应用。这种思路将复杂的子数组操作转化为简单的“差值累加”，时间和空间效率都达到了最优，体现了“化繁为简”的算法设计思维。