# 1526. 形成目标数组的子数组最少增加次数
### 题目地址（1526. 形成目标数组的子数组最少增加次数）
### 题目描述
```
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：
输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 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：
输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2](target) 。
示例 3：
输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2](target)。
示例 4：
输入：target = [1,1,1,1]
输出：1
提示：
1 <= target.length <= 10^5
1 <= target[i] <= 10^5
```
### 前置知识
*
### 公司
* 暂无
### 思路
这道题是要我们将一个全为 0 的数组修改为 nums 数组。我们不妨反着思考，将 nums 改为一个长度相同且全为 0 的数组， 这是等价的。（不这么思考问题也不大，只不过会稍微方便一点罢了）
而我们可以进行的操作是选择一个**子数组**，将子数组中的每个元素减去 1（题目是加 1， 但是我们是反着思考，那么就是减去 1）。
考虑 nums\[0]：
* 其如果是 0，我们没有必要对其进行修改。
* 如果 nums\[0] > 0，我们需要进行 nums\[i] 次操作将其变为 0
由于每次操作都可以选择一个子数组，而不是一个数。考虑这次修改的区间为 \[l, r]，这里 l 自然就是 0，那么 r 取多少可以使得结果最佳呢？
> 我们用 \[l, r] 来描述一次操作将 nums\[l...r]（l和r都包含） 的元素减去 1 的操作。
这实际上取决于 nums\[1], nums\[2] 的取值。
* 如果 nums\[1] > 0，那么我们需要对 nums\[1] 进行 nums\[1] 次操作。（这个操作可能是 l 为 1 的，也可能是 r > 1 的）
* 如果 nums\[1] == 0，那么我们不需要对 nums\[1] 进行操作。
我们的目的就是减少操作数，因此我们可以贪心地求最少操作数。具体为：
1. 找到第一个满足 nums\[i] != 0 的位置 i
2. 先将操作的左端点固定为 i，然后选择右端点 r。对于端点 r，我们需要**先**操作 k 次操作，其中 k 为 min(nums\[r], nums\[r - 1], ..., nums\[i]) 。最小值可以在遍历的同时求出来。
3. 此时 nums\[i] 变为了 nums\[i] - k， nums\[i + 1] 变为了 nums\[i + 1] - k，...，nums\[r] 变为了 nums\[r] - k。**由于最小值 k 为0零，会导致我们白白计算一圈，没有意义，因此我们只能延伸到不为 0 的点**
4. 答案加 k，我们继续使用同样的方法确定右端点 r。
5. i = i + 1，重复 2-4 步骤。
总的思路就是先选最左边不为 0 的位置为左端点，然后**尽可能延伸右端点**，每次确定右端点的时候，我们需要找到 nums\[i...r] 的最小值，然后将 nums\[i...r] 减去这个最小值。这里的”尽可能延伸“就是没有遇到 num\[j] == 0 的点。
这种做法的时间复杂度为 $O(n^2)$。而数据范围为 $10^5$，因此这种做法是不可以接受的。
> 不懂为什么不可以接受，可以看下我的这篇文章：
我们接下来考虑如何优化。
对于 nums\[i] > 0，我们确定了左端点为 i 后，我们需要确定具体右端点 r 只是为了更新 nums\[i...r] 的值。而更新这个值的目的就是想知道它们还需要几次操作。我们考虑如何将这个过程优化。
考虑 nums\[i+1] 和 nums\[i] 的关系：
* 如果 nums\[i+1] > nums\[i]，那么我们还需要对 nums\[i+1] 进行 nums\[i+1] - nums\[i] 次操作。
* 如果 nums\[i+1] <= nums\[i]，那么我们不需要对 nums\[i+1] 进行操作。
如果我们可以把 \[i,r]的操作信息从 i 更新到 i + 1 的位置，那是不是说后面的数只需要看前面相邻的数就行了？
我们可以想象 nums\[i+1] 就是一片木桶。
* 如果 nums\[i+1] 比 nums\[i+2] 低，那么通过操作 \[i,r] 其实也只能过来 nums\[i+1] 这么多水。因此这个操作是从\[i,r]还是\[i+1,r]过来都无所谓。因为至少可以从左侧过来 nums\[i+1] 的水。
* 如果 nums\[i+1] 比 nums\[i+2] 高，那么我们也不必关心这个操作是 \[i,r] 还是 \[i+1,r]。因为既然 nums\[i+1] 都已经变为 0 了，那么必然可以顺便把我搞定。
也就是说可以只考虑相邻两个数的关系，而不必考虑更远的数。而考虑的关键就是 nums\[i] 能够从左侧的操作获得多少顺便操作的次数 m，nums\[i] - m 就是我们需要额为的次数。我们不关心 m 个操作具体是左边哪一个操作带来的，因为题目只是让你求一个次数，而不是具体的操作序列。
### 关键点
* 逆向思考
* 考虑修改的左右端点
### 代码
代码支持：Python3
```python
class Solution:
def minNumberOperations(self, nums: List[int]) -> int:
ans = abs(nums[0])
for i in range(1, len(nums)):
if abs(nums[i]) > abs(nums[i - 1]): # 这种情况，说明前面不能顺便把我改了，还需要我操作 k 次
ans += abs(nums[i]) - abs(nums[i - 1])
return ans
```
**复杂度分析** 令 N 为数组长度。
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
### 相似题目
* [3229. 使数组等于目标数组所需的最少操作次数](https://github.com/azl397985856/leetcode/blob/master/problems/3229.minimum-operations-to-make-array-equal-to-target.md)
### 扩展
如果题目改为：给你一个数组 nums，以及 size 和 K。 其中 size 指的是你不能对区间大小为 size 的子数组执行+1 操作，而不是上面题目的**任意**子数组。K 指的是你只能进行 K 次 +1 操作，而不是上面题目的任意次。题目让你求的是**经过这样的 k 次+1 操作，数组 nums 的最小值最大可以达到多少**。
比如：
```
输入：
nums = [1, 4, 1, 1, 6]
size = 3
k = 2
解释：
将 [1, 4, 1] +1 得到 [2, 5, 2, 1, 6] ，对 [5, 2, 1] +1 得到 [2, 6, 3, 2, 6].
```
解决问题的关键有两点:
* 定义函数 possible(target)，其功能是**在 K 步之内，每次都只能对 size 大小的子数组+1，是否可以满足数组的最小值>=target**。
* 有了上面的铺垫。我们要找的其实就是 possible(target)为 true 的最大的 target。
这里有个关键点，那就是
* 如果 possible(target)为 true。那么 target 以下的都不用看了，肯定都满足。
* 如果 possible(target)为 false。那么 target 以上的都不用看了，肯定都不满足。
也就是说无论如何我们都能将解空间缩小一半，这提示我们使用二分法。结合前面的知识”我们要找的其实就是满足 possible(target) 的最大的 target“，可知道应该使用**最右二分**，如果对最右二分不熟悉的可以看下[二分讲义](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/binary-search)
参考代码：
```py
class Solution:
def solve(self, A, size, K):
N = len(A)
def possible(target):
# 差分数组 d
d = [0] * N
moves = a = 0
for i in range(N):
# a 相当于差分数组 d 的前缀和
a += d[i]
# 当前值和 target 的差距
delta = target - (A[i] + a)
# 大于 0 表示不到 target，我们必须需要进行 +1 操作
if delta > 0:
moves += delta
# 更新前缀和
a += delta
# 如果 i + size >= N 对应我上面提到的只修改左端点，不修改右端点的情况
if i + size < N:
d[i + size] -= delta
# 执行的+1操作小于等于K 说明可行
return moves <= K
# 定义解空间
lo, hi = min(A), max(A) + K
# 最右二分模板
while lo <= hi:
mi = (lo + hi) // 2
if possible(mi):
lo = mi + 1
else:
hi = mi - 1
return hi
```
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
