LeetCode 945. 使数组唯一的最小增量

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
数组 排序 贪心 计数

题目描述

✅ 945. 使数组唯一的最小增量

image-20260928225352559

题意分析

每次可以把一个元素增加 1，求使所有元素互不相同的最少操作次数。最终不要求保持原下标顺序，也不要求相邻值差恰好为 1；原值已经足够大时可以直接保留。题目中的原值非负，代码会先排序。

解法：排序 + 贪心

核心思路

[!blue]

排序后可以按从小到大的原值依次安排目标。设 x <= y，却给它们分配了反向的目标 u > v。因为 v >= y >= x，交换两个目标后，x 仍只需增加到 v，y 也能增加到更大的 u；总增加量不变。因此任意最优方案都能整理成目标值按原值顺序严格递增的方案。

已确定的前一个目标为 prev，当前原值为 num。当前既不能小于原值，又必须大于 prev，所以最小合法目标恰好是 max(num, prev + 1)。

若某个可行安排把当前元素放得更高，将它降到这个最小目标，不会碰到前一个目标，也不会碰到后面更大的目标，只会减少操作。依次这样调整，就得到贪心方案，所以每一步取最小合法值能取得全局最少增量。

把 target - num 加入答案，再令 prev = target。后续只需知道上一目标，不必把所有调整结果写回数组。

解题步骤

  • 将数组升序排序，初始化总操作数 moves = 0。
  • 初始化一个小于所有合法原值的 prev。Go 使用 -1，依赖本题原值非负；Java 使用 Integer.MIN_VALUE。
  • 逐个读取 num，取 target = max(num, prev + 1)，累计 target - num。
  • 将 prev 更新为 target，继续处理后续元素，最终返回 moves。若原值已经严格递增，每项都无需增加。

代码实现

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        int prev = Integer.MIN_VALUE;

        for (int num : nums) {
            // 取不小于原值且严格超过上一目标的最小数。
            int target = Math.max(num, prev + 1);

            // 只累计实际增加量，下一轮使用调整后的目标。
            moves += target - num;
            prev = target;
        }

        return moves;
    }
}

import "sort"

func minIncrementForUnique(nums []int) int {
    sort.Ints(nums)
    moves := 0
    prev := -1

    for _, num := range nums {
        // 取不小于原值且严格超过上一目标的最小数。
        target := num
        if target <= prev {
            target = prev + 1
        }
        // 只累计实际增加量，下一轮使用调整后的目标。
        moves += target - num
        prev = target
    }

    return moves
}

复杂度分析

  • 时间复杂度：$O(n\log n)$。排序后只需一次线性扫描。
  • 空间复杂度：扫描使用 $O(1)$ 额外空间，另计排序的辅助空间。

关键点总结

[!green]

  • 排序前只要求最终值互异，排序后才能把目标统一安排成严格递增序列。
  • 最小合法目标同时满足“不能减小”和“不能与此前目标重复”。
  • prev 保存已经调整后的目标，而非上一项原值。

易错点总结

[!yellow]

  • 只把重复值增加一次，可能仍与前面已经抬高的目标冲突，必须比较 prev。
  • 没有排序就要求目标按原顺序递增，会额外加入题目没有要求的顺序限制。
  • 操作数是每项的 target - num，不是相邻原值差或相邻目标差。
  • 当前实现只把输入排序，后续目标仅用于计算；不能把调用后的数组误认为最终互异结果。

相似题目

题目 难度 关联与区别
1827. 最少操作使数组递增 简单 原题保持原下标顺序并使序列严格递增，本题只要求值互异，可排序后贪心抬高冲突值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/68576875
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！