Hard

题目描述

给你两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 的任意子数组，并将该子数组中的每个元素加 1 或减 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 <= 10^5
  • 1 <= nums[i], target[i] <= 10^8

解题思路

解题思路

这道题的关键在于理解操作的本质：我们可以选择任意子数组进行统一的加1或减1操作。

核心观察：

  1. 将问题转化：设 diff[i] = nums[i] - target[i]，目标是让所有 diff[i] 都变为0
  2. 每次操作相当于选择一个子数组，将其中所有元素统一加1或减1

贪心策略： 使用分治思想。对于数组中的每个位置，我们考虑以下几种情况：

  • 如果当前位置的 diff 值为0，则不需要操作
  • 如果当前位置的 diff 值与前一位置同号，可以复用之前的操作
  • 如果当前位置的 diff 值与前一位置异号，需要新增操作

算法流程：

  1. 计算差值数组 diff[i] = nums[i] - target[i]
  2. 遍历差值数组，对于每个位置：
    • 如果与前一位置同号，可以复用操作，只需要处理差值的增量部分
    • 如果异号或符号改变，需要独立处理
  3. 累加所有必需的操作次数

时间复杂度：O(n)，空间复杂度：O(1)

代码实现

class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        int n = nums.size();
        long long operations = 0;
        long long prev_diff = 0;
        
        for (int i = 0; i < n; i++) {
            long long curr_diff = (long long)nums[i] - target[i];
            
            if (i == 0) {
                operations += abs(curr_diff);
            } else {
                // 如果当前差值与前一个差值同号，可以复用操作
                if ((curr_diff > 0 && prev_diff > 0) || (curr_diff < 0 && prev_diff < 0)) {
                    // 只需要处理增量部分
                    if (abs(curr_diff) > abs(prev_diff)) {
                        operations += abs(curr_diff) - abs(prev_diff);
                    }
                } else {
                    // 异号或者从0开始，需要独立操作
                    operations += abs(curr_diff);
                }
            }
            prev_diff = curr_diff;
        }
        
        return operations;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        n = len(nums)
        operations = 0
        prev_diff = 0
        
        for i in range(n):
            curr_diff = nums[i] - target[i]
            
            if i == 0:
                operations += abs(curr_diff)
            else:
                # 如果当前差值与前一个差值同号，可以复用操作
                if (curr_diff > 0 and prev_diff > 0) or (curr_diff < 0 and prev_diff < 0):
                    # 只需要处理增量部分
                    if abs(curr_diff) > abs(prev_diff):
                        operations += abs(curr_diff) - abs(prev_diff)
                else:
                    # 异号或者从0开始，需要独立操作
                    operations += abs(curr_diff)
            
            prev_diff = curr_diff
        
        return operations

public class Solution {
    public long MinimumOperations(int[] nums, int[] target) {
        int n = nums.Length;
        long operations = 0;
        long prevDiff = 0;
        
        for (int i = 0; i < n; i++) {
            long currDiff = (long)nums[i] - target[i];
            
            if (i == 0) {
                operations += Math.Abs(currDiff);
            } else {
                // 如果当前差值与前一个差值同号，可以复用操作
                if ((currDiff > 0 && prevDiff > 0) || (currDiff < 0 && prevDiff < 0)) {
                    // 只需要处理增量部分
                    if (Math.Abs(currDiff) > Math.Abs(prevDiff)) {
                        operations += Math.Abs(currDiff) - Math.Abs(prevDiff);
                    }
                } else {
                    // 异号或者从0开始，需要独立操作
                    operations += Math.Abs(currDiff);
                }
            }
            prevDiff = currDiff;
        }
        
        return operations;
    }
}

/**
 * @param {number[]} nums
 * @param {number[]} target
 * @return {number}
 */
var minimumOperations = function(nums, target) {
    const n = nums.length;
    const diff = new Array(n);
    
    for (let i = 0; i < n; i++) {
        diff[i] = target[i] - nums[i];
    }
    
    let operations = 0;
    let stack = 0;
    
    for (let i = 0; i < n; i++) {
        if (diff[i] > stack) {
            operations += diff[i] - stack;
        } else if (diff[i] < stack) {
            operations += stack - diff[i];
        }
        stack = diff[i];
    }
    
    operations += Math.abs(stack);
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)