LeetCode 1526. 形成目标数组的子数组最少增加次数
目录
题目描述
题意分析
起点是一个与
target等长的全 0 数组，每次操作可以任选一段连续区间，把区间里每个位置都加 1。问最少操作多少次能把全 0 数组变成target。要的是次数这个数字，不需要还原出具体的操作方案。关键约束是「每次只能加 1，且只能作用在连续区间上」。加 1 而不是加任意值，意味着某个位置的最终值
target[i]恰好等于覆盖它的操作条数；连续区间则意味着一条操作在数组上占据的是一整段，不能跳着覆盖。这两点合起来把问题变成了「用最少的线段去铺满每个位置所需的层数」。数组长度可以到 $10^5$，元素值到 $10^5$，所以按值一层一层模拟必然超时——真实操作次数本身就可能有 $10^5$ 量级，逐次模拟每次还要扫一段区间。规模在提示答案要用一次线性扫描直接算出来。
元素全是正整数（下界为 1），所以每个位置至少要被覆盖一次，不存在「某段完全不用管」的情况。
边界上，长度为 1 的数组答案就是它唯一的元素值；全相等的数组答案是这个公共值，因为一条覆盖全长的操作可以重复使用。
解法：贪心累加正向增量
核心思路
最朴素的想法是模拟：每一轮找出当前还没达标的位置，取其中一段极大连续区间做一次 +1，重复到全部达标。这样操作数是对的，但轮数等于最大元素值，每轮又要扫一遍数组，复杂度到 $O(n \cdot \max)$，$10^5 \times 10^5$ 直接爆掉。
瓶颈在于按「层」推进：每一层都要重新扫描一次数组来划分区间，而层与层之间的区间结构其实高度重复。
换个角度按「列」看。把
target想成一排柱子，target[i]是第i根柱子的高度。每次操作是往一段连续柱子上盖一层砖，所以一条操作在纵向看就是一条水平的线段。总操作数 = 所有线段的条数 = 所有线段左端点的个数。于是问题变成：统计有多少条线段以位置i为左端点。观察相邻两根柱子的高度关系。覆盖位置
i的线段共有target[i]条，覆盖位置i-1的有target[i-1]条。任何一条覆盖了i-1的线段都可以顺势延伸到i（因为区间连续，延长不需要额外代价），所以最多能有min(target[i-1], target[i])条线段是从左边延续过来的。剩下的target[i] - target[i-1]条（当这个差为正时）无处可借，只能新开，也就是必须以i为左端点。如果差为负或为零，说明左边的线段绰绰有余，一条新的都不用开，多出来的那些在i-1处收尾即可，不产生任何成本。由此得到不变量：扫描到下标
i时，累加的答案恰好等于「所有左端点落在[0, i]内的线段条数」。因为每条线段有且只有一个左端点，扫完全数组就把线段不重不漏地数了一遍。最终答案就是target[0] + Σ max(0, target[i] - target[i-1])，其中target[0]相当于把左侧看作高度 0 的虚拟柱子后的首个正增量。这个值同时也是下界（每个正增量必须新开线段）和可达值（负增量处让线段自然结束即可），所以它就是最优解。
解题步骤
- 把答案初始化为
target[0]。这等价于在数组左侧补一根高度为 0 的虚拟柱子，第一根柱子的全部高度都是净新增，没有任何线段能从左边延续过来。- 从下标 1 开始向右扫描，逐个计算
diff = target[i] - target[i-1]。用差分而不是绝对高度，是因为线段能否复用完全取决于相邻两根柱子的高度落差，与绝对高度无关。- 当
diff > 0时把它加进答案。这一部分高度左边确实供不上，必须新开diff条以i为左端点的线段，一条也不能少。- 当
diff <= 0时什么都不做。左边的线段数量已经够用甚至有余，多余的部分在i-1处结束就行，右端点的选择是免费的，所以不贡献任何操作数。- 扫描结束直接返回累加值。不需要回头修正，因为每条线段只在其左端点被计数一次，扫描过程天然完成了去重。
以
target = [3, 1, 5, 4, 2]走一遍：答案初始化为target[0] = 3，对应三条以下标 0 起头的线段。看下标 1，diff = 1 - 3 = -2，非正，不加——原本三条线段里有两条在下标 0 处就收尾，剩一条延续过来正好铺满高度 1。看下标 2，diff = 5 - 1 = 4，为正，答案变成 7——左边只能延续一条，还差四条，必须新开四条以下标 2 为左端点的线段。看下标 3，diff = 4 - 5 = -1，非正，不加——五条里让一条在下标 2 收尾，四条延续过来正好。看下标 4，diff = 2 - 4 = -2，非正，不加——四条里收尾两条，剩两条铺满。扫描结束返回 7。反过来验证：三条线段取[0,0]、[0,0]、[0,4]，四条取[2,2]、[2,3]、[2,3]、[2,4]，逐位累加得到 3、1、5、4、2，恰好还原出target，七条确实做到了。
代码实现
// 当 target[i] > target[i-1] 时，多出的高度只能由以 i 为左端点的操作提供。
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;
}
}
// 当 target[i] > target[i-1] 时，多出的高度只能由以 i 为左端点的操作提供。
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)$。只用了答案累加变量和循环下标，通过
target[i-1]直接读取前一个高度，没有额外开差分数组或栈。
关键点总结
- 「区间加 1 构造目标数组」的对偶问题是「数一共用了多少条线段」，而线段与它的左端点一一对应，把计数落到左端点上就能一次扫描解决，这个转化在所有区间覆盖类题目里都通用。
- 差分是识别信号：一旦发现答案只跟相邻元素的落差有关、跟绝对数值无关，就应该立刻从遍历元素切换到遍历差值。本题答案正是差分数组中所有正项之和。
- 正增量必须新开、负增量可以免费收尾，这种「上坡收费下坡免费」的不对称性是贪心成立的根本原因，也是判断答案下界与可达性一致的依据。
- 首元素要当成「与虚拟 0 的落差」处理，否则整条链的起点会缺失，这是把差分思路落到代码时最常见的偏移错误。
- 面试视角：这题被标为困难，但代码只有五行，考的完全是能否讲清楚「为什么只数正增量就够」。面试时要把「下界」和「可达」两侧都说到——正增量处必须新开线段所以不会更少，负增量处让线段自然结束就能构造出方案所以不会更多，两边一夹答案唯一。只写公式不给证明，即使 AC 也拿不到高分。
易错点总结
- 错误写法：答案初始化为 0，循环从下标 1 开始。用例
target = [3, 1, 5, 4, 2]→ 漏掉首根柱子的 3，返回 4，正确答案是 7。- 错误写法：把所有相邻差的绝对值都累加进答案。用例
target = [1, 3, 1]→ 得到 1 + 2 + 2 = 5，正确答案是 3，下坡处的线段收尾并不需要额外操作。- 错误写法：直接返回数组最大值。用例
target = [1, 5, 1, 5]→ 返回 5，正确答案是 9，因为两个波峰各自要独立开线段，不能共用。- 错误写法：直接返回数组元素之和。用例
target = [2, 2, 2]→ 返回 6，正确答案是 2，一条覆盖全长的线段重复两次即可。- 错误写法：按值逐层模拟，每轮扫描一次数组划分连续段。用例 长度 $10^5$、元素全为 $10^5$ 的数组 → 逻辑正确但要执行 $10^{10}$ 次基本操作，直接超时。
- 错误写法：循环里写成
target[i] - target[i+1]，方向搞反。用例target = [1, 3]→ 越界访问或算出负增量，返回 1，正确答案是 3。- 错误写法：用
if (diff != 0) answer += diff而不是只收正项。用例target = [5, 1]→ 答案变成 5 + (-4) = 1，正确答案是 5。- 错误写法：认为长度为 1 时要特判返回 1。用例
target = [7]→ 返回 1，正确答案是 7，单根柱子的高度就是所需的操作次数。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 370. 区间加法 | 中等 | 本题的逆运算，给定操作列表用差分数组还原最终数组 |
| 1109. 航班预订统计 | 中等 | 差分模板题，区间加的是任意值而非固定的 1 |
| 1094. 拼车 | 中等 | 差分之后还要检查前缀和是否越过容量上限，多一层可行性判定 |
| 135. 分发糖果 | 困难 | 同样靠相邻落差做贪心，但需要左右各扫一遍再取最大值 |
| 42. 接雨水 | 困难 | 同样把数组看成柱状图，关注的是凹陷容积而非覆盖线段数 |
| 84. 柱状图中最大的矩形 | 困难 | 柱状图视角配单调栈，求的是极大矩形面积 |
| 453. 最小操作次数使数组元素相等 | 中等 | 操作对象是「除一个外全部加一」，等价转化为全部向最小值靠拢 |