LeetCode 每日一题笔记 日期：2025.10.30 题目：1526. 形成目标数组的子数组最少增加次数

张开发
• 2026/4/21 14:29:44 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode 每日一题笔记 日期：2025.10.30 题目：1526. 形成目标数组的子数组最少增加次数
LeetCode 每日一题笔记0. 前言日期2025.10.30题目1526. 形成目标数组的子数组最少增加次数难度困难标签: 贪心算法、数组1. 题目理解问题描述给你一个整数数组target和一个数组initialinitial数组与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]就是需要额外增加的操作次数因为前一个元素的“高度”已被覆盖当前元素需要额外的子数组操作来弥补差值。算法步骤特殊情况处理若数组为空直接返回 0。初始化结果res为target[0]基础层操作次数。从第二个元素开始遍历数组若当前元素target[i]大于前一个元素target[i-1]则将差值target[i] - target[i-1]加到res中。遍历结束后res即为最少操作次数。3. 代码实现classSolution{publicintminNumberOperations(int[]target){intres0;restarget[0];for(inti1;itarget.length;i){inttemp(target[i]-target[i-1]0)?target[i]-target[i-1]:0;restemp;}returnres;}}4. 代码优化说明该算法的时间复杂度为 ( O(n) )n是数组长度空间复杂度为 ( O(1) )已经是最优解无需额外优化。5. 复杂度分析时间复杂度( O(n) )仅需遍历一次数组。空间复杂度( O(1) )仅需常数级额外空间。6. 总结本题的核心思路是**“层叠高度差分析”**通过观察相邻元素的差值来计算最少操作次数属于贪心算法的典型应用。这种思路将复杂的子数组操作转化为简单的“差值累加”时间和空间效率都达到了最优体现了“化繁为简”的算法设计思维。

更多文章