2025-03-11：使数组等于目标数组所需的最少操作次数。用go语言，给定两个长度相同的正整数数组 nums 和 target

福大大架构师每日一题

发布于 2025-03-12 14:58:40

4200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-11：使数组等于目标数组所需的最少操作次数。用go语言，给定两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 中的任意连续子数组，并将该子数组内的所有元素都增加或减少 1。

你的目标是计算将 nums 转变为 target 所需的最少操作次数。

1 <= nums.length == target.length <= 100000。

1 <= nums[i], target[i] <= 100000000。

输入： nums = [1,3,2], target = [2,1,4]。

输出： 5。

解释：

执行以下操作可以使 nums 等于 target：

nums[0..0] 增加 1，nums = [2,3,2]。

nums[1..1] 减少 1，nums = [2,2,2]。

nums[1..1] 减少 1，nums = [2,1,2]。

nums[2..2] 增加 1，nums = [2,1,3]。

nums[2..2] 增加 1，nums = [2,1,4]。

答案2025-03-11：

chatgpt[1]

题目来自leetcode3229。

大体步骤如下：

1.初始化变量：

• 定义变量 n 表示数组的长度，将 nums 中第一个元素与 target 中对应位置的元素相减并取最大值作为初始值 ans。

2.循环遍历数组元素：

• 从索引为 1 的元素开始，逐个遍历数组元素。
• 计算当前位置的操作次数：当前位置的目标值减去当前位置的原始值，减去前一个位置目标值与原始值的差值，取结果与 0 的最大值。
• 将上面计算的值加到 ans 中。

3.处理最后一个元素：

• 单独计算最后一个位置的操作次数：目标数组最后一个元素与原始数组最后一个元素的差值，取结果与 0 的最大值。
• 将此次操作次数加到 ans 中。

4.返回最终操作次数 ans。

总的时间复杂度分析：

• 初始化给定数组时间复杂度为 O(1)；
• 遍历数组元素共需循环 n 次，计算每次操作的时间复杂度为 O(1)；
• 最终返回结果时间复杂度为 O(1)。

所以，总的时间复杂度为 O(n)。

总的额外空间复杂度分析：

• 需要常量级别的额外空间来存储变量，不随输入规模变化，额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import"fmt"

func minimumOperations(nums, target []int)int64 {
    n := len(nums)
    ans := max(target[0]-nums[0], 0)
    for i := 1; i < n; i++ {
        ans += max((target[i]-nums[i])-(target[i-1]-nums[i-1]), 0)
    }
    ans += max(-(target[n-1] - nums[n-1]), 0)
    returnint64(ans)
}

func main() {
    nums := []int{1, 3, 2}
    target := []int{2, 1, 4}
    result := minimumOperations(nums, target)
    fmt.Println(result) // 输出结果
}

Python完整代码如下：

# -*-coding:utf-8-*-

defmax(a, b):
    return a if a > b else b

defminimum_operations(nums, target):
    n = len(nums)
    ans = max(target[0] - nums[0], 0)
    
    for i inrange(1, n):
        ans += max((target[i] - nums[i]) - (target[i - 1] - nums[i - 1]), 0)
    
    ans += max(-(target[n - 1] - nums[n - 1]), 0)
    return ans

# 主程序
nums = [1, 3, 2]
target = [2, 1, 4]
result = minimum_operations(nums, target)
print(result)  # 输出结果