使数组唯一的最小增量 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,2]
- 输出
- 1 （把一个 2 抬成 3）
- 输入
- nums=[3,2,1,2,1,7]
- 输出
- 6 （最终变成 [1,2,3,4,5,7]）
最优解：一步一步想明白
- 3记住这套「新占用值 = max(上一个+1, x)，代价 = 新值 - x」，下面每一帧都在套它。
- 4先看原始数组 [3,2,1,2,1,7]，里面有两个 1、两个 2，存在重复，需要把它们抬开。
- 5排序后变成 [1,1,2,2,3,7]。相同的数挨在一起，从左往右处理就只需盯住「前一个占用值」。y 先设成 -1，这样第 0 个数的下一个可用值是 0，不会误抬。
- 6轮到第 0 个数 1（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 -1，所以现在能用的最小值是 0。
- 71 已经不小于 0，自己就够大，直接占用 1，这一步代价是 0，一步都不用花。
- 81 原地锁定为绿色，代价 0，总代价还是 0。下一个数要比 1 更大。
- 9轮到第 1 个数 1（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 1，所以现在能用的最小值是 2。
- 102 比 1 大，说明 1 占不下，会和前面重复（标红）。只能把它抬到刚好不撞的 2，多走 1 步。
- 11把它从 1 抬到 2，绿色锁定。总代价累加到 1，下一个数要比 2 更大才行。
- 12轮到第 2 个数 2（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 2，所以现在能用的最小值是 3。
- 133 比 2 大，说明 2 占不下，会和前面重复（标红）。只能把它抬到刚好不撞的 3，多走 1 步。
- 14把它从 2 抬到 3，绿色锁定。总代价累加到 2，下一个数要比 3 更大才行。
- 15轮到第 3 个数 2（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 3，所以现在能用的最小值是 4。
- 164 比 2 大，说明 2 占不下，会和前面重复（标红）。只能把它抬到刚好不撞的 4，多走 2 步。
- 17把它从 2 抬到 4，绿色锁定。总代价累加到 4，下一个数要比 4 更大才行。
- 18轮到第 4 个数 3（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 4，所以现在能用的最小值是 5。
- 195 比 3 大，说明 3 占不下，会和前面重复（标红）。只能把它抬到刚好不撞的 5，多走 2 步。
- 20把它从 3 抬到 5，绿色锁定。总代价累加到 6，下一个数要比 5 更大才行。
- 21轮到第 5 个数 7（紫色）。左边绿色的都是已经定下来、互不重复的值。前一个占用到 5，所以现在能用的最小值是 6。
- 227 已经不小于 6，自己就够大，直接占用 7，这一步代价是 0，一步都不用花。
- 237 原地锁定为绿色，代价 0，总代价还是 6。下一个数要比 7 更大。
- 24全部处理完，数组变成 [1,2,3,4,5,7]，每个值都不一样。把每一步的代价加起来正好是 6，这就是答案。
⚠️ 容易写错的地方
✗ 错：不排序直接贪心
✓ 对：必须先排序
只有排序后，每个数才只需和「前一个占用值」比较，否则要兼顾全局会出错
✗ 错：抬过头，不是刚好比前一个大 1
✓ 对：抬到 max(y+1, x) 这个最小合法值
抬到更大的值只会多花代价，贪心要取最小可用值
✗ 错：用集合暴力找下一个空位
✓ 对：排序后线性递推 y
每次从某值往上找空位，最坏会退化成平方级，数据大就超时
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n log n)
排序占主导，之后一遍线性扫描
空间
O(1)
只用 y、ans 两个变量；排序自身栈开销另算
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使数组唯一的最小增量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不排序能不能做？+
能。还有一种计数法：先统计每个值出现的次数，从小到大扫描值域，把某个值上多出来的重复数往后「顺延」到下一个值，同样累加代价。它是 O(n + 值域) 的，当值域不大时更快；排序法则是 O(n log n) 但实现最短，面试里写排序贪心最稳。
怎么证明贪心是对的？+
排序后从左到右，第 i 个数能占用的最小合法值，必然不小于前一个占用值加 1。取这个最小值，本步代价最小，而且它是后续所有数的下界里最松的，不会逼后面花更多。用交换论证：若某步抬得更高，把多出的部分省下来不会让任何后续步骤变差，所以最小值方案不劣于任何方案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使数组唯一的最小增量 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。