Skip to content

Latest commit

 

History

History
211 lines (166 loc) · 5.78 KB

README.md

File metadata and controls

211 lines (166 loc) · 5.78 KB
comments difficulty edit_url rating source tags
true
困难
2066
第 407 场周赛 Q4
栈
贪心
数组
动态规划
单调栈

3229. 使数组等于目标数组所需的最少操作次数

English Version

题目描述

给你两个长度相同的正整数数组 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 <= 105
  • 1 <= nums[i], target[i] <= 108

解法

方法一：动态规划

我们可以先计算出 $\textit{nums}$ 和 $\textit{target}$ 两个数组的差值，然后对于一个差值数组，我们找出连续的差值符号相同的区间，然后对于每个区间，我们将第一个元素的绝对值加到结果中，然后对于后面的元素，如果差值的绝对值比前一个差值的绝对值大，那么我们将绝对值的差值加到结果中。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

相似题目：

Python3

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

Java

class Solution {
    public long minimumOperations(int[] nums, int[] target) {
        long f = Math.abs(target[0] - nums[0]);
        for (int i = 1; i < nums.length; ++i) {
            long x = target[i] - nums[i];
            long y = target[i - 1] - nums[i - 1];
            if (x * y > 0) {
                long d = Math.abs(x) - Math.abs(y);
                if (d > 0) {
                    f += d;
                }
            } else {
                f += Math.abs(x);
            }
        }
        return f;
    }
}

C++

class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        using ll = long long;
        ll f = abs(target[0] - nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            long x = target[i] - nums[i];
            long y = target[i - 1] - nums[i - 1];
            if (x * y > 0) {
                ll d = abs(x) - abs(y);
                if (d > 0) {
                    f += d;
                }
            } else {
                f += abs(x);
            }
        }
        return f;
    }
};

Go

func minimumOperations(nums []int, target []int) int64 {
	f := abs(target[0] - nums[0])
	for i := 1; i < len(target); i++ {
		x := target[i] - nums[i]
		y := target[i-1] - nums[i-1]
		if x*y > 0 {
			if d := abs(x) - abs(y); d > 0 {
				f += d
			}
		} else {
			f += abs(x)
		}
	}
	return int64(f)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript

function minimumOperations(nums: number[], target: number[]): number {
    const n = nums.length;
    let f = Math.abs(target[0] - nums[0]);
    for (let i = 1; i < n; ++i) {
        const x = target[i] - nums[i];
        const y = target[i - 1] - nums[i - 1];
        if (x * y > 0) {
            const d = Math.abs(x) - Math.abs(y);
            if (d > 0) {
                f += d;
            }
        } else {
            f += Math.abs(x);
        }
    }
    return f;
}