#179. 最大数

• LeetCode：179. 最大数
• 难度：中等
• 归类：贪心、字符串、自定义排序
• 主解法：按照两种拼接结果的大小排序

#先给结论

这道题不能按数值大小或普通字符串顺序排序。对于两个数字字符串 a 和 b，只需比较：

a + b
b + a

• 如果 a + b > b + a，就把 a 放在 b 前面。
• 如果 a + b < b + a，就把 b 放在 a 前面。
• 如果两者相等，二者先后顺序不影响最终结果。

按这个规则排序后连接所有字符串，就是能够组成的最大数。

#题目描述

给定一组非负整数 nums，重新排列每个数的顺序，使它们连接后组成最大的整数。每个整数不可拆分。

由于结果可能非常大，必须返回字符串。

示例 1：

输入：nums = [10, 2]
输出："210"

示例 2：

输入：nums = [3, 30, 34, 5, 9]
输出："9534330"

题目约束：

• 1 <= nums.length <= 100。
• 0 <= nums[i] <= 10^9。

#为什么普通排序不行

按数值降序排列 [3, 30] 会得到：

30 + 3 = "303"

但正确顺序是：

3 + 30 = "330"

普通字符串降序也不可靠。例如 "121" 在普通字典序中大于 "12"，但：

"121" + "12" = "12112"
"12" + "121" = "12121"

所以 "12" 应放在 "121" 前面。决定顺序的不是单个字符串本身，而是两种拼接结果。

#自定义比较规则

定义：

a 应排在 b 前面 ⇔ a + b > b + a

例如：

a + b 和 b + a 的长度始终相同，并且只包含数字，所以可以直接使用字符串字典序比较，不需要转换成数值。

#为什么排序后是全局最优

考虑任意排列中相邻的两个字符串 a 和 b，其余前缀和后缀分别记为 P 和 S：

P + a + b + S

如果 a + b < b + a，交换二者后得到：

P + b + a + S

两个完整字符串的公共前缀 P 相同，公共后缀 S 也不影响首次出现差异的位置。因为 b + a 更大，所以交换后的完整结果一定更大。

因此，任何最优排列都不能包含违反比较规则的相邻逆序对。按照 a + b 与 b + a 的规则排序，会消除所有这样的逆序对，所以得到全局最大结果。

#比较规则为什么满足传递性

排序比较器必须保持一致，不能出现 a 应在 b 前、b 应在 c 前，但 c 又应在 a 前的循环关系。

关系：

a + b >= b + a

等价于比较无限周期字符串：

aaaaaa…
bbbbbb…

普通字典序具有传递性，因此这个拼接比较规则也具有传递性，可以安全地交给排序算法使用。若两种拼接相等，交换它们不会改变最终字符串。

#JavaScript 精度陷阱

不能把拼接结果转换成 Number 后相减：

return Number(b + a) - Number(a + b);

题目允许单个数字达到 10^9，两个数字拼接后最多有 20 位，已经超过 JavaScript 的安全整数范围。不同字符串可能被舍入成相同的 Number。

例如：

a = "888888878"
b = "88888887"

a + b = "88888887888888887"
b + a = "88888887888888878"

正确结果是 a + b 更大，但这两个字符串转换成 Number 后会得到相同的浮点数。比较器会错误地返回 0。

正确做法是直接比较等长字符串：

if (a + b > b + a) {
    return -1;
}

#示例推演

以 nums = [3, 30, 34, 5, 9] 为例：

• "9" + "5" > "5" + "9"，所以 "9" 在 "5" 前。
• "5" + "34" > "34" + "5"，所以 "5" 在 "34" 前。
• "34" + "3" > "3" + "34"，所以 "34" 在 "3" 前。
• "3" + "30" > "30" + "3"，所以 "3" 在 "30" 前。

排序结果：

["9", "5", "34", "3", "30"]

连接后得到：

"9534330"

#代码实现

参考实现来源：doocs/leetcode，按本文的字符串比较方式重新整理，避免 JavaScript 大整数精度问题；原项目采用 CC BY-SA 4.0。

#JavaScript 实现

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function (nums) {
    const values = nums.map((num) => String(num));

    values.sort((a, b) => {
        const ab = a + b;
        const ba = b + a;

        if (ab === ba) {
            return 0;
        }

        return ab > ba ? -1 : 1;
    });

    if (values[0] === '0') {
        return '0';
    }

    return values.join('');
};

#代码与思路对照

#全零情况

如果排序后第一个字符串是 "0"，说明所有元素都是 0。因为任意非零字符串与 "0" 比较时都会排在 "0" 前面。

因此：

[0, 0, 0] → "0"

而不是：

"000"

只检查排序后的第一个元素即可，不需要删除结果中的每一个前导零。

#边界与陷阱

• 单个元素： 直接返回它的字符串形式。
• 全部为零： 必须返回 "0"。
• 包含零但不全为零： 非零元素会排在零前面，例如 [0, 1, 0] → "100"。
• 前缀相同： 不能只比较第一位或普通字典序，例如 "12" 与 "121"。
• 拼接结果相等： 例如 "12" 与 "1212"，任意顺序都产生相同结果。
• 不要转成 Number： 拼接值可能超过安全整数范围。
• 不要返回数值： 最终结果可能远超 JavaScript 可精确表示的范围。
• 输入数组： 当前实现先创建字符串数组，不会修改原始 nums。

#复杂度分析

设数组长度为 n，单个整数转换后的最大位数为 k：

• 时间复杂度：O(nk log n)。排序需要 O(n log n) 次比较，每次拼接和比较至多处理 O(k) 个字符。
• 额外空间复杂度：O(nk)。字符串数组保存所有数字的字符串形式；排序算法自身的额外空间取决于 JavaScript 引擎，但不会改变该上界。

题目中 k <= 10，把位数视为常数时，也可以简写为时间 O(n log n)、额外空间 O(n)。返回字符串占用的空间不计入额外空间。

#面试官递进追问

#1. 为什么不能直接按数值从大到小排序？

数值大小只描述单个数字，不描述拼接后的相对贡献。例如 30 > 3，但 "330" > "303"，所以 3 应在 30 前面。

#2. 为什么比较的是 a + b 和 b + a？

两个元素在最终结果中相邻时只有这两种顺序。选择更大的拼接顺序，无论它们前后还有什么内容，都不会让完整结果变小。

#3. 如何证明局部交换能得到全局最优？

如果一个排列中存在相邻逆序对 a、b，并且 a + b < b + a，交换它们会严格增大完整字符串。不断消除逆序对后得到的排序结果不存在可改进的相邻交换，因此是全局最优。

#4. 这个比较规则满足传递性吗？

满足。a + b >= b + a 等价于比较 a 和 b 的无限周期字符串；字典序具有传递性，所以不会形成循环比较关系。

#5. 为什么不能使用 Number(ba) - Number(ab)？

两个输入拼接后最多有 20 位，超过 JavaScript 的安全整数范围，转换时可能丢失低位差异，使本应有先后顺序的元素被错误地视为相等。

#6. 为什么排序后首元素为 "0" 就代表全是零？

任何非零字符串按照拼接规则都会排在 "0" 前面。如果 "0" 仍位于首位，就不可能存在非零元素。

#7. 如果 a + b === b + a 怎么办？

返回 0 即可。这类字符串通常具有相同的重复模式，例如 "12" 和 "1212"；无论谁在前，局部乃至最终拼接结果都相同。

#8. 为什么复杂度不是简单的 O(n log n)？

排序比较器不是常数成本：它需要拼接并比较最多 2k 个字符。完整表达是 O(nk log n)；只有把题目限定的最大位数 k <= 10 视为常数时，才简写为 O(n log n)。

#常见错误

• 按数值大小或普通字符串字典序排序。
• 只比较两个数字的首位。
• 使用数值减法比较拼接结果，忽略 JavaScript 精度上限。
• 比较器方向写反，得到最小拼接数。
• 忘记把全零结果规范化为 "0"。
• 返回数值而不是字符串。
• 声称额外空间为 O(1)，忽略字符串数组和排序空间。

#可迁移总结

• 拼接排序： 两个元素的相对顺序由两种局部拼接结果决定。
• 交换论证： 证明交换逆序相邻元素会改善整体结果，从而说明排序规则全局正确。
• 比较器安全： 自定义比较器不仅要符合目标，还要满足传递性。
• 语言边界： 数字字符串很长时应直接比较字符串，避免浮点精度问题。
• 一句话记忆： 若 a + b > b + a，就让 a 排在 b 前面。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么比较 a + b 和 b + a 就能决定两个元素的相对顺序？