LeetCode 179. 最大数
目录
题目描述
✅ 179. 最大数
题意分析
给一组非负整数，要求重新排列它们的先后顺序，把所有数首尾相接拼成一个数，使这个数尽可能大，并以字符串形式返回。
为什么返回值是字符串？这是题目给出的最强信号：数组最多 100 个元素，每个元素最大 $10^9$，拼接结果可以长达上千位，远远超出
long的表示范围。任何「拼完转成整数再比大小」的想法从一开始就不可行，全程只能在字符串层面操作。另一个必须提前想到的边界是全 0 输入：比如
[0, 0]，无论怎么排列拼出来都是"00"，但作为数它就是 0，正确答案应当是"0"而不是一串零。单元素数组、所有元素相同等退化输入也应能自然处理。
解法：按拼接结果自定义排序
核心思路
问题关键：数值大小不能决定拼接顺序，例如
3 > 30，但真正有用的比较是"330" > "303"。因此对任意两个字符串a、b，若a + b > b + a（+表示拼接），就让a排在前面。为什么选该解法：枚举排列需要 $O(n!)$；自定义排序只需 $O(n \log n)$ 次比较。该比较等价于比较两个字符串无限循环后的字典序，因此具有传递性，可以交给排序算法。
正确性依据：若一个排列中相邻的
a、b满足a + b < b + a，交换它们会让整体结果变大。排序后的序列不存在这种逆序对，所以无法再通过交换得到更优排列，即为全局最优。最后若首元素是"0"，说明所有数都是 0，答案统一返回"0"。
解题步骤
- 将每个整数转成字符串，避免拼接结果溢出。
- 按
(b + a).compareTo(a + b)排序，使更优的拼接顺序在前。- 若排序后第一个字符串是
"0"，直接返回"0"。- 否则依次拼接所有字符串。
例如
[3, 30, 34, 5, 9]排序为[9, 5, 34, 3, 30]，得到"9534330"。
代码实现
class Solution {
public String largestNumber(int[] nums) {
String[] values = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
values[i] = String.valueOf(nums[i]);
}
Arrays.sort(values, (a, b) -> (b + a).compareTo(a + b));
if ("0".equals(values[0])) {
return "0";
}
return String.join("", values);
}
}
func largestNumber(nums []int) string {
values := make([]string, len(nums))
for i, num := range nums {
values[i] = strconv.Itoa(num)
}
sort.Slice(values, func(i int, j int) bool {
// 比较两种拼接顺序，决定谁应该排在前面。
return values[i]+values[j] > values[j]+values[i]
})
if values[0] == "0" {
return "0"
}
return strings.Join(values, "")
}
复杂度分析
- 时间复杂度：$O(nm \log n)$，
m为数字的最大位数；排序有 $O(n \log n)$ 次比较，每次比较两种拼接需要 $O(m)$。- 空间复杂度：$O(nm)$，用于保存字符串及结果；排序栈和比较时的临时字符串不改变该上界。
关键点总结
- 比较的是
a + b和b + a，不是a、b的数值或普通字典序。- 交换论证解释了局部比较为何能得到全局最优，这是面试时需要说清的部分。
- 全程使用字符串；排序后首项为
"0"时统一返回"0"。
易错点总结
- 比较器方向写反：
[10, 2]会得到"102"，正确答案是"210"。- 直接按数值或普通字典序降序：
[3, 30]、[12, 121]都会排错。- 将拼接串转成整数再比较：结果可能远超
long，应直接比较等长字符串。- 忘记全 0 特判：
[0, 0]应返回"0"，不是"00"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 45. 把数组排成最小的数 | 中等 | 同款拼接比较器但方向取反，求最小且无需全 0 特判 |