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 的求和。该和就是答案。
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
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“，可知道应该使用最右二分，如果对最右二分不熟悉的可以看下二分讲义
参考代码：
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 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago