LeetCode 179. 最大数
题目描述
✅ 179. 最大数
题意分析
给定一个非空的非负整数数组，重新排列这些整数，再把它们的十进制表示首尾相接，使得到的数最大。每个整数必须完整使用一次，不能拆开其中的数字，也不能只挑选一部分整数。
结果可能超过整数类型的范围，因此返回字符串。所有排列的总位数相同，差别在于数字出现的先后顺序；目标是让越靠前的位置尽可能大。若输入全部为零，结果统一写成单个
"0"。
解法：按拼接结果自定义排序
核心思路
[!blue]
先决定任意两个数字字符串
a、b谁排在前面。它们只有a + b与b + a两种拼接顺序，应选择较大的那个。两串长度相同，所以可以直接按字典序比较，不需要转成整数；单独比较a、b的数值或字典序，则没有考虑另一项紧接在后面的影响。这个局部规则能决定整体最优。若某个排列中相邻的
a、b不符合规则，交换它们只改变对应的这段字符：前面的前缀完全相同，两项总长度不变，后面的后缀位置也不变。因此更大的局部拼接一定让整个结果更大。不断消除这些相邻逆序，就能得到不劣于任意初始排列的排序结果。比较规则也具有传递性，可以交给排序函数。设
a、b的数值为A、B，位数为p、q，比较a + b与b + a等价于比较A * (10^q - 1)与B * (10^p - 1)，也就是比较A / (10^p - 1)与B / (10^q - 1)。这些比值能形成一致的大小关系；此处只用于说明排序成立，代码仍使用字符串比较，避免精度与溢出问题。Java 的比较器返回
(b + a).compareTo(a + b)，使较优的a排在前面；Go 则直接返回a + b > b + a。若两种拼接相同，两项的相对次序不会影响答案。排序后依次连接所有字符串即可。任意正数都会排在零前面，因此排序后的第一项若为
"0"，就说明全部元素都是零，此时直接返回"0"。
解题步骤
- 将每个整数转换成字符串，保存到
values。- 自定义比较器，比较两项交换顺序后的完整拼接结果，让较大的顺序在前。
- 检查排序后的第一项，若为
"0"，返回单个"0"。- 否则按排序结果依次连接所有字符串并返回。
代码实现
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);
}
}
import (
"sort"
"strconv"
"strings"
)
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)$，
n为整数个数，m为最大位数。排序需要 $O(n \log n)$ 次比较，每次构造并比较两种拼接最多花费 $O(m)$；转换与最终连接共 $O(nm)$。- 空间复杂度：$O(nm)$，保存各整数的字符串及最终结果。比较时的临时字符串为 $O(m)$，排序所需空间不改变整体上界。
关键点总结
[!green]
- 每个整数是不可拆分的一块，排序依据是两块交换次序后的拼接结果。
- 相邻交换不会改变前后其他块的位置，较大的局部拼接就对应较大的整体结果。
- 比较规则相等时可以任意排列；全零输入需要单独规范化为
"0"。
易错点总结
[!yellow]
- 按数值或普通字符串字典序排序，无法处理位数不同或一项是另一项前缀时的先后关系。
- Java 比较器的返回方向与 Go 的布尔判定写法不同；两者都要让较大的拼接顺序靠前。
- 将拼接字符串转成整数再比较可能溢出；两种拼接本来就等长，直接比较字符串即可。
- 比较结果相等时应允许两项并列，Go 比较函数不能写成
>=。- 忘记全零判断，会返回多个连续的零，而非题目要求的单个
"0"。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 45. 把数组排成最小的数 | 中等 | 两题都比较a+b与b+a来决定相邻顺序，原题取最小，本题取最大。 |