LeetCode 题解工作台
使数组等于目标数组所需的最少操作次数
给你两个长度相同的正整数数组 nums 和 target 。 在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。 返回使 nums 数组变为 target 数组所需的 最少 操作次数。 示例 1： 输入： nums = [3,5,1,2], target …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们可以先计算出 和 两个数组的差值，然后对于一个差值数组，我们找出连续的差值符号相同的区间，然后对于每个区间，我们将第一个元素的绝对值加到结果中，然后对于后面的元素，如果差值的绝对值比前一个差值的绝对值大，那么我们将绝对值的差值加到结果中。 时间复杂度 ，其中 为数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个长度相同的正整数数组 nums 和 target。
在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。
返回使 nums 数组变为 target 数组所需的 最少 操作次数。
示例 1：
输入： nums = [3,5,1,2], target = [4,6,2,4]
输出： 2
解释：
执行以下操作可以使 nums 等于 target：
- nums[0..3] 增加 1，nums = [4,6,2,3]。
- nums[3..3] 增加 1，nums = [4,6,2,4]。
示例 2：
输入： 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]。
提示：
1 <= nums.length == target.length <= 1051 <= nums[i], target[i] <= 108
解题思路
方法一：动态规划
我们可以先计算出 和 两个数组的差值，然后对于一个差值数组，我们找出连续的差值符号相同的区间，然后对于每个区间，我们将第一个元素的绝对值加到结果中，然后对于后面的元素，如果差值的绝对值比前一个差值的绝对值大，那么我们将绝对值的差值加到结果中。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
相似题目：
class Solution:
def minimumOperations(self, nums: List[int], target: List[int]) -> int:
n = len(nums)
f = abs(target[0] - nums[0])
for i in range(1, n):
x = target[i] - nums[i]
y = target[i - 1] - nums[i - 1]
if x * y > 0:
d = abs(x) - abs(y)
if d > 0:
f += d
else:
f += abs(x)
return f
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for familiarity with dynamic programming and greedy algorithms.
- question_mark
Candidate should demonstrate an understanding of how to minimize operations via subarray manipulation.
- question_mark
Interviewer may want to see an efficient solution involving space-time trade-offs.
常见陷阱
外企场景- error
Misunderstanding the problem and trying to apply simple operations without considering subarray manipulations.
- error
Failing to optimize the solution for large arrays, resulting in excessive time or space complexity.
- error
Ignoring edge cases such as arrays where nums and target are already equal, which could result in an unnecessary increase in operations.
进阶变体
外企场景- arrow_right_alt
Changing the operation constraint from only subarrays to any segment.
- arrow_right_alt
Introducing more complex operations such as multiplication or division within the transformation.
- arrow_right_alt
Allowing partial matching or approximations of nums to target.