标签： 差分

目标

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。

请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：

• 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1：

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2：

输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3：

输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4：

输入：target = [1,1,1,1]
输出：1

说明：

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

思路

有一个 target 数组和一个与其维度相同的的全 0 数组 initial，每次操作可以将 initial 任意子数组的每个元素加 1。求将 initial 变为 target 的最小操作次数。

将子数组全部加一很容易想到差分数组，按照贪心的思想，要将元素从 0 操作为 target[i] 一定需要 target[i] 次，问题在于有多少个元素可以共用这一个操作。

计算差分数组，仅统计其中大于 0 的部分，小于等于 0 说明可以公用前面的操作，大于 0 说明需要增加操作。

代码

/**
 * @date 2025-10-30 8:57
 */
public class MinNumberOperations1526 {

    public int minNumberOperations(int[] target) {
        int n = target.length;
        int res = target[0];
        for (int i = 1; i < n; i++) {
            int diff = target[i] - target[i - 1];
            if (diff > 0) {
                res += diff;
            }
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9
• 0 <= numOperations <= nums.length

思路

对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。

与 3346.执行操作后元素的最高频率I 相比，本题的数据范围更大，无法枚举值域。

考虑使用差分数组，由于数据范围太大，使用有序集合来维护。差分数组的前缀就是可以操作成该元素的频率，它不能超过原来已有的个数 + 操作次数。

代码

/**
 * @date 2025-10-21 10:34
 */
public class MaxFrequency3347 {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> diff = new TreeMap<>();
        for (int num : nums) {
            cnt.merge(num, 1, Integer::sum);
            diff.putIfAbsent(num, 0);
            diff.merge(num - k, 1, Integer::sum);
            diff.merge(num + k + 1, -1, Integer::sum);
        }
        int res = 0;
        int frequency = 0;
        for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
            frequency += entry.getValue();
            res = Math.max(res, Math.min(frequency, cnt.getOrDefault(entry.getKey(), 0) + numOperations));
        }
        return res;
    }
}

性能