# 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 啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://p.ipic.vip/cwgl6d.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1526.minimum-number-of-increments-on-subarrays-to-form-a-target-array.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.