最大数问题为什么要按拼接结果排序？自定义比较器怎么证明？

简化版

最大数不是按数字大小排序，而是把数字转成字符串后，比较两个数 a、b 的拼接结果：如果 a+b > b+a，就让 a 排在 b 前面。比如 9 和 34，934 > 349，所以 9 在前；3 和 30，330 > 303，所以 3 在前。排序后拼接即可，若首位是 0，说明全是 0，返回 "0"。

详细版

这题的核心是“局部相邻顺序决定全局拼接大小”。对于任意两个字符串数字 a 和 b，它们在最终结果中相邻时只有两种顺序：ab 或 ba。如果 ab 更大，那么让 a 在前不会变差；如果 ba 更大，就让 b 在前。用这个规则作为比较器排序，拼接后的字符串就是最大结果。

String largestNumber(int[] nums) {
    String[] arr = new String[nums.length];
    for (int i = 0; i < nums.length; i++) arr[i] = String.valueOf(nums[i]);
    Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));
    if (arr[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String s : arr) sb.append(s);
    return sb.toString();
}

不能按数值降序，因为 30 < 3 但 330 > 303，3 应排在 30 前。也不能只按首位字符，因为 9、91、910 需要继续比较拼接结果。复杂度主要来自排序，若有 n 个数、平均字符串长度为 m，比较一次拼接近似 O(m)，总时间约 O(n log n * m)。

完整版教学

一、这题考的不是普通降序，而是拼接顺序

最大数问题的输入是若干非负整数，输出它们拼接后能形成的最大字符串。看似是排序，实际比较对象不是单个数字大小，而是“谁放前面能让整体更大”。数字 30 比 3 大吗？作为数字不是，但在拼接里 330 大于 303，所以 3 必须排在 30 前。

用例 [3,30,34,5,9] 若按数字降序得到 34,30,9,5,3，拼接是 3430953，明显不如正确答案 9534330。排序依据必须从“单个值大小”切换到“两两拼接贡献”。这是面试官最想听到的观察。

比较对象	例子	得到顺序	是否正确
数值大小	30 > 3	30 在 3 前	错
字典序	”34” > “3”	34 在 3 前	未必
拼接结果	”3”+“30” > “30”+“3”	3 在 30 前	对

二、比较器为什么写成 a+b 和 b+a

对于任意两个候选 a、b，如果它们在最终答案中相邻，那么影响结果的只有 ab 与 ba 两种排列。若 ab > ba，把 a 放在 b 前面，最终字符串在这一段更大；若 ba > ab，就把 b 放前面。这个规则可以直接变成排序比较器。

例如 a="9"、b="34"，ab="934"，ba="349"，所以 9 在前。a="12"、b="121"，ab="12121"，ba="12112"，所以 12 在前。它避免了“只看第一位相同怎么办”的问题，因为拼接比较会自动继续比较后续字符。

若 a+b > b+a，则 a 应排在 b 前
若 a+b < b+a，则 b 应排在 a 前
若 a+b = b+a，则两者相对顺序不影响最终答案

记忆钩子：最大数比较的不是“谁大”，而是“谁站前面后，和对方组成的两位组合更大”。

三、为什么局部比较能推出全局最优

可以用交换论证理解正确性。假设某个排列已经是最优，但其中存在相邻两个元素 a、b 满足 ba > ab，也就是它们当前顺序不如交换后。把这两个元素交换，其他位置不变，整体字符串只在这一小段从 ab 变成 ba，结果会更大，这和“原排列最优”矛盾。

因此最优排列中不应该存在任何“相邻逆序”的 pair。按 a+b 与 b+a 排序后，任意相邻元素都满足局部最优顺序，整体就没有可改进的相邻交换。这个证明和冒泡排序式的交换思想很像：只要还能通过相邻交换变大，就不是最终最大。

原结果：prefix + a + b + suffix
若 b+a > a+b
交换后：prefix + b + a + suffix
因为 prefix 相同，suffix 相同，中间段更大，所以整体更大

四、代码实现细节：字符串比较和全 0 处理

实现时先把整数转成字符串，避免数值拼接溢出。比较器通常写成 (b+a).compareTo(a+b)，这是为了让排序结果按“能产生更大拼接”的顺序降序排列。Java 里比较器返回负数表示第一个参数排前，所以用 b+a 和 a+b 的顺序要看清楚。

全 0 是一个必考边界。输入 [0,0] 排序后拼接会得到 "00"，但题目期望 "0"。排序完成后如果第一个字符串是 "0"，说明最大元素都是 0，直接返回 "0"。这是比最后去掉前导零更简单且更安全的写法。

Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));
if (arr[0].equals("0")) return "0";

五、复杂度不能只写 O(n log n)

排序有 O(n log n) 次比较，但每次比较不是 O(1)，因为要比较 a+b 与 b+a。若平均数字长度是 m，那么拼接和比较的成本近似 O(m)，总时间可以写成 O(n log n * m)。空间上，字符串数组需要 O(nm)，拼接结果也需要 O(nm)。

带数字算一下：如果 n=10000，平均长度 m=5，那么排序比较次数约 10000 * log2(10000) ≈ 132877，每次比较最多看 10 个字符，字符级比较量约百万级。这里 m 通常很小，所以瓶颈仍主要表现为排序。

项目	复杂度	原因
转字符串	O(nm)	每个数字转为字符
排序	O(n log n * m)	比较拼接字符串
拼接答案	O(nm)	构造最终结果
额外空间	O(nm)	字符串数组和结果

六、比较器的工程风险

很多语言的排序要求比较器满足一致性，否则可能抛异常或排序结果不稳定。a+b 与 b+a 这套规则在最大数问题中是可用的，但实现时要避免返回布尔值、避免用整数解析拼接结果，也不要用减法比较，拼接后可能超过 64 位整数范围。

如果语言里字符串拼接在比较器中成本较高，可以缓存字符串形式，或者用自定义字符比较避免临时创建 a+b 和 b+a。不过面试里通常优先写清楚正确性，再补充优化点。不要为了优化把代码写得难以验证，比较器题最怕“看似聪明但顺序错”。

比较 "8308" 和 "830"
"8308830" > "8308308"
所以 "8308" 应排在 "830" 前

七、常见误区与追问

误区：按数字从大到小排序即可。 3 和 30 会反例击穿，拼接目标和数字大小不是同一个目标。
误区：按字符串字典序降序即可。 字典序只能比较单个字符串，无法表达 a 在 b 前还是 b 在 a 前对整体的影响。
误区：拼接后转整数比较更直观。 拼接结果可能非常长，会溢出；应该保留字符串比较。
追问：为什么这个比较器能得到全局最优？ 用相邻交换证明：若存在 ba > ab 的相邻逆序，交换后整体变大，所以最优解不能有这种逆序。
追问：全是 0 怎么处理？ 排序后首位为 "0" 就说明所有元素都是 0，直接返回 "0"。
追问：复杂度为什么带 m？ 比较器每次比较拼接字符串，字符长度参与成本，所以更准确是 O(n log n * m)。

八、加强记忆

最大数题要把“排序键”从单个数字改成相邻拼接贡献。任意两个数 a、b，谁在前只看 a+b 和 b+a 谁大；这个局部规则通过相邻交换论证保证全局最优。代码上先转字符串，用比较器排出最大拼接顺序，最后处理全 0。看到 3/30、12/121 这类反例，就能立刻提醒自己不要按数字或普通字典序排序。

简化版

详细版