## 题目地址（1526. 形成目标数组的子数组最少增加次数）

https://leetcode-cn.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

## 题目描述

```
给你一个整数数组 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

```

## 前置知识

- 差分与前缀和

## 公司

- 暂无

## 思路

首先我们要有前缀和以及差分的知识。这里简单讲述一下：

- 前缀和 pres：对于一个数组 A [1,2,3,4]，它的前缀和就是 [1,1+2,1+2+3,1+2+3+4]，也就是 [1,3,6,10]，也就是说前缀和 $pres[i] =\sum_{n=0}^{n=i}A[i]$
- 差分数组 d：对于一个数组 A [1,2,3,4]，它的差分数组就是 [1,2-1,3-2,4-3]，也就是 [1,1,1,1]，也就是说差分数组 $d[i] = A[i] - A[i-1](i > 0)$，$d[i] = A[i](i == 0)$

前缀和与差分数组互为逆运算。如何理解呢？这里的原因在于你对 A 的差分数组 d 求前缀和就是数组 A。前缀和对于求区间和有重大意义。而差分数组通常用于**先对数组的若干区间执行若干次增加或者减少操作**。仔细看这道题不就是**对数组若干区间执行 n 次增加操作**，让你返回从一个数组到另外一个数组的最少操作次数么？差分数组对两个数字的操作等价于原始数组区间操作，这样时间复杂度大大降低 O(N) -> O(1)。

题目要求**返回从 initial  得到   target  的最少操作次数**。这道题我们可以逆向思考**返回从 target  得到  initial   的最少操作次数**。

这有什么区别么？对问题求解有什么帮助？由于  initial 是全为 0 的数组，如果将其作为最终搜索状态则不需要对状态进行额外的判断。这句话可能比较难以理解，我举个例子你就懂了。比如我不反向思考，那么初始状态就是 initial ，最终搜索状态自然是 target ，假如我们现在搜索到一个状态 state.我们需要**逐个判断 state[i] 是否等于 target[i]**，如果全部都相等则说明搜索到了 target ，否则没有搜索到，我们继续搜索。而如果我们从 target  开始搜，最终状态就是  initial，我们只需要判断每一位是否都是 0 就好了。 这算是搜索问题的常用套路。

上面讲到了对差分数组求前缀和可以还原原数组，这是差分数组的性质决定的。这里还有一个特点是**如果差分数组是全 0 数组，比如[0, 0, 0, 0]，那么原数组也是[0, 0, 0, 0]**。因此将 target 的差分数组 d 变更为 全为 0 的数组就等价于 target 变更为 initaial。

如何将 target 变更为 initaial？

由于我们是反向操作，也就是说我们可执行的操作是 **-1**，反映在差分数组上就是在 d 的左端点 -1，右端点（可选）+1。如果没有对应的右端点+1 也是可以的。这相当于给原始数组的 [i,n-1] +1，其中 n 为 A 的长度。

如下是一种将 [3, -2, 0, 1] 变更为 [0, 0, 0, 0] 的可能序列。

```
[3, -2, 0, 1] -> [**2**, **-1**, 0, 1] -> [**1**, **0**, 0, 1] -> [**0**, 0, 0, 1] -> [0, 0, 0, **0**]
```

可以看出，上面需要进行四次区间操作，因此我们需要返回 4。

至此，我们的算法就比较明了了。

具体算法：

- 对 A 计算差分数组 d
- 遍历差分数组 d，对 d 中 大于 0 的求和。该和就是答案。

```py
class Solution:
    def minNumberOperations(self, A: List[int]) -> int:
        d = [A[0]]
        ans = 0

        for i in range(1, len(A)):
            d.append(A[i] - A[i-1])
        for a in d:
            ans += max(0, a)
        return ans
```

**复杂度分析**
令 N 为数组长度。

- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$

实际上，我们没有必要真实地计算差分数组 d，而是边遍历边求，也不需要对 d 进行存储。具体见下方代码区。

## 关键点

- 逆向思考
- 使用差分减少时间复杂度

## 代码

代码支持：Python3

```python
class Solution:
    def minNumberOperations(self, A: List[int]) -> int:
        ans = A[0]
        for i in range(1, len(A)):
            ans += max(0, A[i] - A[i-1])
        return ans
```

**复杂度分析**
令 N 为数组长度。

- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$

## 扩展

如果题目改为：给你一个数组 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://github.com/azl397985856/leetcode/blob/master/91/binary-search.md)

参考代码：

```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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
