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

2023-09-16 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

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

题意分析

每次操作只能挑一个元素加 1，问最少操作多少次才能让数组里的元素两两不同。返回的是操作次数总和，不是最终数组，所以只要能算出「每个元素最终落在哪个值上」，答案就是所有位移量之和。

只能加不能减，这个单向性是全题的骨架：一个元素永远不会往下走，因此小的值天然拥有优先权，大的值只能被往上顶。如果允许双向调整，题目会变成完全不同的匹配问题。

约束里 n 到十万量级、元素值在 0 到十万之间，两个上界同阶。这暗示两条路都通：一条是先让元素之间产生确定的先后关系再逐个安置，另一条是直接在值域上开桶统计每个值挤了多少个元素、把多出来的往后推。两者复杂度分别是 $O(n \log n)$ 与 $O(n + C)$。

边界上要注意：数组可能本来就无重复，此时答案是 0；可能全是同一个值，此时位移量呈 0、1、2、…、n-1 的等差累加，规模能到十亿量级，累加器的类型要心里有数；另外单元素数组和空数组都应返回 0，且元素被推到超过原始值域上界是完全合法的，不需要做任何截断。

解法：排序 + 贪心

核心思路

暴力做法是反复扫描数组，每发现一个重复值就把它加 1，再重新检查一遍，直到没有重复为止。最坏情况（比如 10^5 个相同的值）要扫描 $O(n)$ 轮、每轮 $O(n)$，还要在每轮内部做去重判断，总代价高达 $O(n^3)$ 或 $O(n^2 \log n)$，完全不可行。

瓶颈在于「谁该让位、让到哪里」这个决策被反复推翻：同一个元素可能先被推到某个位置，过一会儿又和别人撞上，再被推一次。每次推进都只用了局部信息，没有一个能一次性定死结果的顺序。

关键观察是：既然只能增不能减，那么在最终方案里，元素之间的相对大小顺序一定和原数组的排序结果一致。理由是交换论证——若原本 $a \le b$，最终却让 a 落到了比 b 更大的位置，把这两个终点互换，两段位移之和只会更小或不变，且仍然合法。既然顺序被固定，就可以按从小到大依次给元素分配终点，每个元素只需要满足「比前一个已分配的终点大」这一个条件，而且在满足条件的前提下取尽可能小的值一定最优：把它放得更高不会给后面的元素带来任何好处，只会让后面的下界更高、总位移更大。

于是不变量可以写成：从小到大处理元素时，用 prev 记录上一个元素最终落到的值，则当前元素的终点必然是 max(num, prev + 1)。取 num 意味着它本来就够大、不用动；取 prev + 1 意味着它被挤到了紧挨着前一个的位置，一格都不多让。答案就是每一步 终点 - 原值 的累加。

需要留意 prev 的初值：第一个元素不应受任何约束，所以 prev 必须小于所有可能的元素值，用一个足够小的哨兵即可，保证 max(num, prev + 1) 一定取到 num。

解题步骤

先对数组升序排序。整个贪心建立在「按最终大小顺序依次分配」之上，而这个顺序就是原数组的排序结果；不排序的话 prev 记录的不是「所有已处理元素中的最大终点」，后面元素的下界就是错的。

把 moves 初始化为 0，prev 初始化为一个极小哨兵。moves 累加的是位移总量；哨兵的作用是让第一个元素走 max(num, prev + 1) = num 这条分支，从而不产生任何多余位移。Java 用 Integer.MIN_VALUE，Go 用 -1 << 60，两者都远小于题目值域下界 0。

顺序遍历每个 num，令 target = max(num, prev + 1)。这一行同时覆盖了两种情况：num > prev 说明它天然合法，原地不动；num <= prev 说明它和前面撞了或被前面盖过，必须被顶到 prev + 1。写成一个 max 而不是 if/else，是因为两个分支的语义本来就是「取二者较大」。

累加 moves += target - num。差值就是这个元素被加了多少次 1。不动时差值为 0，自然不影响结果，不需要额外判断。

更新 prev = target。注意更新的是调整后的值而不是原值，否则后面的元素会以为下界还停在原地，从而分配到已被占用的位置。

遍历结束返回 moves。因为每一步都取了满足约束的最小终点，累加起来就是全局最小操作数。

以 nums = [3, 2, 1, 2, 1, 7] 走一遍：排序后是 [1, 1, 2, 2, 3, 7]，moves = 0，prev 为哨兵。第一个 1：target = max(1, 哨兵+1) = 1，位移 0，moves = 0，prev = 1。第二个 1：target = max(1, 2) = 2，位移 1，moves = 1，prev = 2。第一个 2：target = max(2, 3) = 3，位移 1，moves = 2，prev = 3。第二个 2：target = max(2, 4) = 4，位移 2，moves = 4，prev = 4。3：target = max(3, 5) = 5，位移 2，moves = 6，prev = 5。7：target = max(7, 6) = 7，位移 0，moves = 6，prev = 7。返回 6。最终数组是 [1, 2, 3, 4, 5, 7]，确实两两不同，且总共加了 1 + 1 + 2 + 2 = 6 次。

代码实现

// 若当前值小于等于 prev，则增加到 prev + 1 并累加增量。
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;
    }
}

// 若当前值小于等于 prev，则增加到 prev + 1 并累加增量。
func minIncrementForUnique(nums []int) int {
    sort.Ints(nums)
    moves := 0
    prev := -1 << 60

    for _, num := range nums {
        target := num
        if target <= prev {
            target = prev + 1
        }
        moves += target - num
        prev = target
    }

    return moves
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 n 为数组长度。凭什么？排序是 $O(n \log n)$，之后只有一趟线性扫描，每个元素做常数次比较、减法与赋值，没有回溯也没有二次扫描；因此总时间被排序主导。若改用值域计数的桶做法，可以做到 $O(n + C)$，其中 C 是值域大小。

空间复杂度：$O(\log n)$。凭什么？算法本身只维护 moves 与 prev 两个标量，是 $O(1)$；额外空间全部来自排序的递归栈深度。相比之下计数解法需要一个长度为 $C + n$ 的桶数组，空间是 $O(C + n)$，这正是两种解法的取舍点。

关键点总结

单向操作意味着顺序不变，顺序不变意味着可以按序贪心：只能加不能减，最终排列必然与原排序同序，于是「安排所有元素」就退化成「从小到大依次给每个元素找最小合法位置」。凡是操作只有一个方向的题，都值得先问一句「相对顺序会不会被打乱」。

贪心的正确性来自「多让一格没有任何收益」：给某个元素分配比 prev + 1 更大的终点，只会抬高后续元素的下界，总位移单调变差。能把这句话说清楚，就等于给出了交换论证式的证明。

用 max 统一两个分支比写 if/else 更不容易错：target = max(num, prev + 1) 天然处理了「不用动」和「被顶上去」两种情况，也避免了漏掉「相等」这一边界（相等时必须挪，因为要求两两不同）。

状态更新一定要用调整后的值：prev = target 而不是 prev = num，这是本题最高频的一处笔误，也是所有「维护已占用边界」类贪心的通用要点。

哨兵初值要严格小于值域下界：题目值域从 0 起，所以任何负数哨兵都可用，但要保证 prev + 1 不会溢出——Integer.MIN_VALUE + 1 是安全的，Long.MIN_VALUE 强转 int 就不是。

面试视角：给出排序贪心之后，主动补一句「值域和 n 同阶时还有 $O(n + C)$ 的计数解法：先统计每个值出现次数，从小到大扫值域，把多余的元素累积成一个待安置的数量，遇到空位就放一个进去并累加位移」，能直接展示出对复杂度取舍的敏感度，是这道题的加分点。

易错点总结

错误写法：忘记排序直接线性扫描。用例 nums = [3, 2, 1, 2, 1, 7] → 按原序处理，3 之后 prev = 3，接着 2 被顶到 4、1 被顶到 5、2 被顶到 6、1 被顶到 7、7 被顶到 8，总位移 2 + 4 + 4 + 6 + 1 = 17，正确答案是 6；顺序错了，贪心的前提就没了。

错误写法：prev = num 而不是 prev = target。用例 nums = [1, 1, 1] → 三个元素的 prev 一直停在 1，第二个和第三个都被算成 max(1, 2) = 2，位移各 1、总和 2，且最终数组是 [1, 2, 2] 仍有重复；正确答案是 3（终点为 1、2、3）。

错误写法：判断条件写成 num < prev 而漏掉相等。用例 nums = [1, 1] → 第二个 1 不满足 1 < 1，被认为无需调整，返回 0；正确答案是 1，因为题目要求元素两两不同，相等同样必须挪走。

错误写法：prev 初始化为 0。用例 nums = [0, 0] → 第一个 0 被算成 max(0, 1) = 1，白白产生 1 次位移，总和变成 1 + 2 = 3，正确答案是 1；值域含 0 时用 0 当哨兵会误伤第一个元素。

错误写法：累加写成 moves += target 而不是 moves += target - num。用例 nums = [1, 1] → 两个终点是 1 和 2，累加终点得到 3，而正确答案是位移之和 0 + 1 = 1；累加的对象必须是「加了多少次 1」，不是「最终落在哪」。

错误写法：用哈希集合模拟「占位」，冲突就一直加 1 直到找到空位。用例 10^5 个相同的值 → 第 k 个元素要试探 k 次，总试探次数约 $5 \times 10^9$，直接超时；排序后每个元素的终点是一步算出来的，不需要探测。

错误写法：累加器用 int 且不考虑量级。用例 10^5 个相同的大值 → 位移总和约 $5 \times 10^9$ 超过 int 上限，Java 里会回绕成负数返回一个负的操作数。Go 的 int 是 64 位不受影响，Java 保险起见可以用 long 累加、最后再转回。

错误写法：以为答案是「重复元素的个数」。用例 nums = [1, 1, 1] → 重复元素两个，但答案是 3（一个加 1、一个加 2）。被顶走的元素可能引发连锁推进，位移量不等于冲突数量。

错误写法：为了「省事」在原数组上边改边比较，却又提前退出。用例 nums = [1, 2, 2, 3] → 若在把第二个 2 改成 3 后就认为数组已唯一并退出，会漏掉它与后面那个 3 的新冲突；正确答案是 [1, 2, 3, 4] 共 1 + 1 = 2 次。必须一趟走完全部元素。

错误写法：Go 里用 sort.Slice 但比较函数写成 >。用例 nums = [3, 2, 1, 2, 1, 7] → 数组变成降序 [7, 3, 2, 2, 1, 1]，每个元素都被顶到前一个之上，返回 24 这类远大于 6 的值；整型切片直接用 sort.Ints 即可。

相似题目

题目	难度	考察点
41. 缺失的第一个正数	困难	同样利用值域与下标的对应关系，但要求原地置换且只查找空位不做位移累加
448. 找到所有数组中消失的数字	简单	只需标记出未被占用的槽位，不涉及冲突元素往后顺延的连锁推进
462. 最小操作次数使数组元素相等 II	中等	目标是全部相等而非全部不同，操作可增可减，最优点落在中位数上
135. 分发糖果	困难	同为「相邻约束下取最小总量」的贪心，但约束是双向的，需要左右各扫一遍
1046. 最后一块石头的重量	简单	同样按大小顺序做局部决策，但数据在过程中动态变化，需要堆而非一次排序
621. 任务调度器	中等	也是把冲突项往后错开安排，但错开的间隔固定，答案由最高频任务的桶结构决定