使数组唯一的最小增量 图解题解

每次把某个数加 1，最少几次能让值都不同

给整数数组 nums，一次操作把某个下标的值加 1，只能加不能减。要让每个值都唯一，问最少操作多少次。题面例子 nums=[1,2,2] 只需 1 次，把一个 2 加成 3；nums=[3,2,1,2,1,7] 要 6 次，最终变成 [1,2,3,4,5,7]。难点在于重复的数不止一个，往哪顶、顶到几还互相牵扯。

见一个重复就去找空位，为什么会越找越慢

先想到的多半是扫出重复的数，挑一个没被占用的新值。可「没被占用」得对着整个数组查，通常拿集合记下已用的值，遇到重复就从它往上一格格试到空位。数据一大，最坏每个重复数都要探很多格，退化成平方级，几万个数就超时。而且顶到哪个值才不多花，散着看理不清。

先排好序，每个数只跟前一个占用值较劲

把 nums 从小到大排序，相同的数就挨在一起，重复只发生在相邻位置。这样每个数不必顾全局，只要保证比左边刚定下来的占用值大就行。

记左边最后占用的值为 y，轮到当前数 x：若 x 已经比 y 大，它自己就够，原地占用、一步不花；若 x ≤ y，会撞上前面，得把它抬到 y+1，这是躲开重复的最小合法值。为什么抬到刚好 y+1、不多抬？多抬一格，当前多花代价，还把后面所有数的下限顶高，只会更贵；抬到 y+1 既躲开重复，又给后面留最大空间。每步取最小可用值，合起来抬升量最小。

把「抬到刚好」压成一行递推

用变量 y 记上一个占用值，初始设成 -1，让第一个数的可用下限落在 0，非负的数都不用抬。ans 记累计代价从 0 起。遍历排序后每个 x：占用值 y = max(y+1, x)，要么被前一个逼到 y+1、要么就是 x 自己，取大的那个；代价 y − x 累加进 ans。走完返回 ans。x ＞ y 时代价 0，x ≤ y 时补上和 y+1 的差距。

[3,2,1,2,1,7] 排完序，6 是怎么一步步加出来的

排序后是 [1,1,2,2,3,7]，起手 y=-1、ans=0。第一个 1：y=max(0,1)=1，代价 1−1=0，ans=0。第二个 1：y=max(2,1)=2，顶到 2，代价 2−1=1，ans=1。

第一个 2：y=max(3,2)=3，顶到 3，代价 3−2=1，ans=2。第二个 2：y=max(4,2)=4，顶到 4，代价 4−2=2，ans=4。3：y=max(5,3)=5，顶到 5，代价 5−3=2，ans=6。7：y=max(6,7)=7，自己够大，代价 0，ans 停在 6。数组落成 [1,2,3,4,5,7]，六个值互不相同，累计正是 6。

三个会让你多花步数或直接超时的地方

不排序直接贪心是头号坑：一个数得和前面所有已定的值逐一比较，逻辑绕不清、容易漏判撞车。抬过头是第二个：只要抬到 max(y+1, x)，多抬哪怕一格，当前多花一步，后面所有数的下限被顶高，代价滚成雪球。第三个是拿集合暴力找空位，一格格往上探，最坏退化成平方级就卡死。

时间上，排序 O(n log n)，之后只线性扫一趟，仍是 O(n log n)；除了 y 和 ans 没另开空间，O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans, y = 0, -1
        for x in nums:
            y = max(y + 1, x)
            ans += y - x
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, y = -1;
        for (int x : nums) {
            y = max(y + 1, x);
            ans += y - x;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, y = -1;
        for (int x : nums) {
            y = Math.max(y + 1, x);
            ans += y - x;
        }
        return ans;
    }
}