LeetCode 179. 最大数：贪心策略与全序关系证明

1. 题目解析

题目来源

测试用例

2. 算法原理

这道题的核心在于如何定义'大'的概念。我们需要将数组中的数字组合成一个最大的整数，这意味着高位数字越大越好。

如果直接比较数值大小排序（例如 3 和 30），简单的数值比较无法解决拼接后的顺序问题（330 vs 303）。因此，我们将所有整数转换为字符串，通过自定义比较规则来决定顺序。

贪心策略： 对于任意两个字符串 s1 和 s2，如果 s1 + s2 > s2 + s1，则 s1 应该排在 s2 前面。这样能保证局部最优解最终导向全局最优解。

边界情况处理： 需要注意的是，当数组中全部是 0 时（例如 [0, 0]），按上述逻辑拼接会得到 "00"。但根据题意，结果应返回单个字符 "0"。因此，在生成最终字符串后，需要检查首位是否为 '0'，如果是，直接返回 "0"。

为什么只需判断第一个位置？ 因为由排序的底层逻辑可知，当第一位都是字符 "0" 时，代表此时整个字符串必定全部为 "0"，所以只需要判断第一个即可。

3. 实战代码

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;
        // 将整数转为字符串，便于拼接比较
        for(auto e : nums) {
            str.push_back(to_string(e));
        }
        
        // 自定义排序规则：比较拼接后的字符串大小
        sort(str.begin(), str.end(), [](const string& s1, const string& s2) {
            return s1 + s2 > s2 + s1;
        });
        
        string ret;
        (& e : str) {
            ret += e;
        }
        
        
         ret[] ==  ?  : ret;
    }
};