179. 最大数

题目链接（中等）

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

数据范围：

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

示例

示例 1：

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

示例 2：

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

核心思路

要使拼接后的字符串字典序最大，需要确定一种排序规则。

对于两个数字字符串 a 和 b：

• 如果 a + b > b + a，则 a 应该排在 b 前面；
• 如果 a + b < b + a，则 b 应该排在 a 前面；
• 如果相等，顺序无所谓。

为什么这样排序是对的？

假设最优排列中 b 在 a 前面，但 a + b > b + a。交换 a 和 b 后，整体拼接结果会变大，与“最优”矛盾。因此最优排列必须满足 a + b >= b + a，即按上述规则排序。

全 0 的特殊情况：

如果排序后第一个字符串是 "0"，说明所有数字都是 0，直接返回 "0"，避免返回 "000..."。

方法：自定义排序

思路及解法

1. 将所有数字转为字符串；
2. 使用自定义比较器排序：
   • 若 a + b > b + a，a 排在前面；
   • 否则 b 排在前面；
3. 拼接排序后的字符串；
4. 若结果首位为 '0'，返回 "0"。

Python 3 中 sort 不再支持 cmp 参数，需要用 functools.cmp_to_key 包装比较函数。

代码

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: list[int]) -> str:
        # 转为字符串
        strs = list(map(str, nums))

        # 自定义比较器：a+b 与 b+a 比较
        def compare(a: str, b: str) -> int:
            if a + b > b + a:
                return -1      # a 排在 b 前面
            elif a + b < b + a:
                return 1       # b 排在 a 前面
            else:
                return 0

        strs.sort(key=cmp_to_key(compare))

        # 拼接结果
        res = ''.join(strs)

        # 处理全 0 的情况
        if res[0] == '0':
            return "0"

        return res

复杂度分析

• 时间复杂度：$O(n \log n \cdot k)$，其中 n 是数组长度，k 是字符串平均长度。排序需要 $O(n \log n)$ 次比较，每次比较拼接字符串，代价 $O(k)$。
• 空间复杂度：$O(n \cdot k)$，存储所有字符串和排序结果。

关键细节

1. 为什么比较 a + b 和 b + a

因为最终结果是所有字符串的拼接，两个字符串的相对顺序只影响它们拼接后的局部顺序。要让整体最大，就应让局部拼接 a + b 尽可能大。

2. 排序规则的方向

Python 的 sort 默认升序，compare(a, b) 返回负数表示 a 应排在 b 前面。

• a + b > b + a 时，a 应该在前，返回 -1；
• a + b < b + a 时，b 应该在前，返回 1。

3. 全 0 的处理

例如 nums = [0, 0]，排序后拼接得到 "00"，但正确答案是 "0"。因此需要检查结果首位是否为 '0'。

4. 不能用普通数值排序

不能直接按数值大小排序，也不能简单按字符串字典序排序。例如 "9" 和 "34"，数值上 34 > 9，但拼接 "934" > "349"，所以 "9" 应排在 "34" 前面。

5. 比较器的传递性

a + b > b + a 这种比较关系满足传递性，因此可以安全地作为排序规则使用。

总结

• 核心思想：自定义排序，比较 a + b 和 b + a；
• 排序规则：a + b > b + a 时 a 在前；
• 全 0 处理：结果首位为 '0' 时返回 "0"；
• 时间复杂度 $O(n \log n \cdot k)$，空间复杂度 $O(n \cdot k)$；
• 通用套路：「拼接后比较大小」→ 自定义排序。

相关题目

• LC 45. 跳跃游戏 II（贪心）
• LC 56. 合并区间（排序 + 贪心）
• LC 435. 无重叠区间（排序 + 贪心）
• LC 973. 最接近原点的 K 个点（排序）