Skip to content

Latest commit

 

History

History
209 lines (143 loc) · 8.89 KB

1526.minimum-number-of-increments-on-subarrays-to-form-a-target-array.md

File metadata and controls

209 lines (143 loc) · 8.89 KB
Raw

题目地址（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

前置知识

公司

  • 暂无

思路

这道题是要我们将一个全为 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$，因此这种做法是不可以接受的。

不懂为什么不可以接受，可以看下我的这篇文章：https://lucifer.ren/blog/2020/12/21/shuati-silu3/

我们接下来考虑如何优化。

对于 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

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)$

相似题目

扩展

如果题目改为：给你一个数组 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 啦。

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