179. 最大数

这个题，如果用简单的数字进行比较，肯定是行不通的，例如样例2的输入[3,30,34,5,9]，如果单纯比较大小，30比9大，但是930反而是比309更大的。如果转换成字符串，用字典序排序，又存在3和30,因为3没有第二位，第一位又相同，就导致30字典序更大排在前面，但是330是比303更大的。

既然全局来看很复杂，能不能考虑局部，使用贪心的策略来解决，假如现在只有A和B两个数字，就有两种拼法，分别是A+B和B+A，如果$A+B>B+A$，那么最后拼的顺序，A一定是在B前面的，然后拓展到3个数字A，B，C，如果A比B大，A也比C大，A就应该在最前面，然后B和C比，C更大的话C就应该在B前面，拼的顺序就是ACB。

这样我们就可以知道这个题目的解法了。把所有的数据转成字符串。两两拼接比较进行一个排序，最后再把结果拼成一个完整的字符串。就得到了最终的答案。

from functools import cmp_to_key


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        num_strs = list(map(str, nums))

        def compare(x, y):
            if x + y > y + x:
                return -1
            return 1

        num_strs.sort(key=cmp_to_key(compare))
        res = "".join(num_strs)
        if num_strs[0] == "0":
            return "0"
        return res

这里我们需要使用到functools库里面的cmp_to_key函数，因为sort函数的key参数使用lambda的时候，只可以接受一个参数，而不能接受两个参数。所以需要我们写一个自定义的比较函数compare，然后通过cmp_to_key对这个函数进行一个包装，来让sort的key参数可以接受这个函数来进行比较。

这里的返回值的话也是有一定的讲究的，sort默认是升序的，也就是x<y?，是的话x就排y前面，我们这样写之后，sort在比较x和y的时候就从x<y?变成了compare(x,y)<0?是的话就让x排y前面，否则就让x排y后面。所以在compare内部，x+y>y+x的时候，我们返回的是一个负值，符合这个判断让x放在前面，其他情况返回的是一个正值。

题目最后也有一个小细节需要注意一下，那就是我们需要判断一下字符串的首位是不是0,是0应该直接返回0,假如输入是[0,0,0]，结果拼接之后就是"000",这显然是不合理的，题目求的是最大数，只不过很大才需要我们变成字符串返回，对于正常的数字，前缀自然是不能有多余的0。