LeetCode 1526. 形成目标数组的子数组最少增加次数
题目描述
题意分析
初始数组与
target等长，全部为零。一次操作可以选择任意非空连续区间，把其中每个位置都加一，求最终恰好得到target的最少操作次数。区间可以重叠，但只允许增加，不能先超过目标再减少。题目只要最少次数，不要求真的输出这些区间，也不需要模拟每一次加一。
解法：贪心累加正向增量
核心思路
[!blue]
把每次操作看作一个覆盖若干相邻位置的区间。每个位置最终值，就是覆盖它的操作区间数量。因此问题转化为：用尽量少的区间，让每个位置被覆盖指定次数。
第一个位置需要
target[0]次覆盖，这些操作无法从左侧延续过来，至少需要从这里开始这么多个区间。向右处理时，若当前目标比左侧高出diff，延续过来的区间最多只有左侧覆盖数量，差额至少需要diff个新开始的区间。所以“首项 + 所有相邻正差”是任何方案都无法低于的操作数下界。下降并不产生新的下界，因为可以让多余区间在前一项结束。
这个下界也能达到：维持当前覆盖的区间数量等于目标高度，上升时新开差额数量的区间，持平时全部延续，下降时结束多余区间。每次新开对应一次实际操作，延续或结束不会新增操作，且每个位置的覆盖数恰好正确。
因为同一个公式既是下界，又有明确构造能够达到，它就是最少次数。只需累加这些新开数量，无需记录具体区间。
解题步骤
- 将答案初始化为首项
target[0]。- 从第二项开始计算当前值减去前一项的差。
- 差为正时累加到答案，差非正时不增加。
- 扫描完返回总数，输入数组无需修改。
代码实现
class Solution {
public int minNumberOperations(int[] target) {
// 首项相对初始零高度，需要这些区间覆盖。
int answer = target[0];
for (int i = 1; i < target.length; i++) {
int diff = target[i] - target[i - 1];
// 正增量至少需要新开相应数量的区间，下降只需结束旧区间。
if (diff > 0) {
answer += diff;
}
}
return answer;
}
}
func minNumberOperations(target []int) int {
// 首项相对初始零高度，需要这些区间覆盖。
answer := target[0]
for i := 1; i < len(target); i++ {
diff := target[i] - target[i-1]
// 正增量至少需要新开相应数量的区间，下降只需结束旧区间。
if diff > 0 {
answer += diff
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每对相邻目标值检查一次。
- 空间复杂度：$O(1)$，只保存答案和当前差值。
关键点总结
[!green]
- 操作区间数量对应覆盖层数，正差要求新开区间。
- 下界来自必须补足的覆盖缺口，延续与结束区间的构造保证可达。
- 下降只是结束已有操作的作用范围，不需要额外花费。
易错点总结
[!yellow]
- 对相邻差取绝对值，会把下降也算作新操作，重复收费。
- 只看全局最大值，无法反映低谷隔开的多个高段需要分别新开区间。
- 忘记首项会漏掉从零升到第一处高度的全部覆盖。
- 逐次模拟加一会按目标数值重复工作，而需要统计的只是新开始的次数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 370. 区间加法 | 中等 | 原题给区间增加操作求结果，本题给最终数组求最少操作，差分中的正增量就是必须新开的操作数。 |
| 3229. 使数组等于目标数组所需的最少操作次数 | 困难 | 原题从一般初始数组出发且允许整段增减，本题从全0出发只允许增加，是更简单的差分情形。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！