3810. 达到目标数组的最小操作次数

Medium

题目描述

给你两个长度为 n 的整数数组 nums 和 target，其中 nums[i] 是索引 i 处的当前值，target[i] 是索引 i 处的期望值。

你可以执行以下操作任意次（包括零次）：

• 选择一个整数值 x
• 找到所有值为 x 的最大连续段（如果不能向左或向右扩展并保持所有值都等于 x，则段是最大的）
• 对于每个这样的段 [l, r]，同时更新：
  • nums[l] = target[l], nums[l + 1] = target[l + 1], …, nums[r] = target[r]

返回使 nums 等于 target 所需的最少操作次数。

示例 1：

输入：nums = [1,2,3], target = [2,1,3]
输出：2
解释：
- 选择 x = 1：最大段 [0, 0] 被更新 -> nums 变为 [2, 2, 3]
- 选择 x = 2：最大段 [0, 1] 被更新 -> nums 变为 [2, 1, 3]
因此，需要 2 次操作将 nums 转换为 target。

示例 2：

输入：nums = [4,1,4], target = [5,1,4]
输出：1
解释：
- 选择 x = 4：最大段 [0, 0] 和 [2, 2] 被更新 -> nums 变为 [5, 1, 4]
因此，需要 1 次操作将 nums 转换为 target。

示例 3：

输入：nums = [7,3,7], target = [5,5,9]
输出：2
解释：
- 选择 x = 7：最大段 [0, 0] 和 [2, 2] 被更新 -> nums 变为 [5, 3, 9]
- 选择 x = 3：最大段 [1, 1] 被更新 -> nums 变为 [5, 5, 9]
因此，需要 2 次操作将 nums 转换为 target。

约束条件：

• 1 <= n == nums.length == target.length <= 10^5
• 1 <= nums[i], target[i] <= 10^5

解题思路

这道题的关键在于理解操作的本质：每次操作可以选择一个值 x，然后将所有值为 x 的最大连续段同时更新为对应的目标值。

核心思路：

我们只需要关注 nums[i] != target[i] 的位置，因为这些位置需要被修改。根据题意提示，答案就是这些需要修改位置上 nums 中不同值的个数。

为什么这样是对的？

1. 如果某个位置 nums[i] != target[i]，那么这个位置必须在某次操作中被修改
2. 每次选择值 x 进行操作时，所有值为 x 的最大连续段都会被同时更新
3. 因此，对于每个在需要修改位置上出现的不同值，我们至少需要一次操作
4. 贪心策略：对于每个不同的值，我们可以在一次操作中处理所有包含该值的段

算法步骤：

1. 遍历数组，找出所有 nums[i] != target[i] 的位置
2. 统计这些位置上 nums[i] 的不同值的个数
3. 返回不同值的个数即为最小操作次数

这个贪心策略是最优的，因为我们不能用更少的操作完成任务——每个不同的值至少需要被选择一次。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& target) {
        unordered_set<int> distinctValues;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != target[i]) {
                distinctValues.insert(nums[i]);
            }
        }
        
        return distinctValues.size();
    }
};

class Solution:
    def minOperations(self, nums: List[int], target: List[int]) -> int:
        distinct_values = set()
        
        for i in range(len(nums)):
            if nums[i] != target[i]:
                distinct_values.add(nums[i])
        
        return len(distinct_values)

public class Solution {
    public int MinOperations(int[] nums, int[] target) {
        HashSet<int> distinctValues = new HashSet<int>();
        
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] != target[i]) {
                distinctValues.Add(nums[i]);
            }
        }
        
        return distinctValues.Count;
    }
}

var minOperations = function(nums, target) {
    const distinctValues = new Set();
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== target[i]) {
            distinctValues.add(nums[i]);
        }
    }
    
    return distinctValues.size;
};

复杂度分析

其中 n 是数组长度，k 是需要修改位置上不同值的个数（最坏情况下 k = n）。