本文主要是介绍「贪心算法」最大数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣原题链接，点击跳转。
有一个整数数组，我们可以按照任意顺序把这些数拼接成一个新的整数，如2、3和10可以拼接为2310、3102、2103等等。能拼出来的最大整数是多少呢？由于这个数可能非常大，所以结果是一个字符串。
很自然的想法是，把这些数按照某种方式排个序，然后再拼接到一起。假设a和b拼接出来的数是ab或ba，如2和10拼接出来的数是210和102。如果ab>ba，那么就把a放在前面，否则把b放在前面。此时，任意给定两个数a和b，我们都能确定谁先谁后，自然就能对整个数组排序了（其实这个说法不太严谨，因为是否能排序的问题还需要更加严格的证明，感兴趣的读者可以试着证一下）。在对这个数组排完序之后，放在前面更容易拼接成更大数的数，自然都被放在了前面。最后把这个数组的所有数拼接到一起，就是最终结果，这个最终结果一定是能拼出来的最大的数，感兴趣的读者可以试着证明这一点。
根据ab和ba的大小关系确定a和b的先后顺序的过程，就是贪心策略。比较ab和ba的大小，可以先转换为字符串，再比较字符串的字典序。最后还有一个小细节，如果数组里面全都是0，最终拼出来的字符串就是一串0，但是要返回0。
class Solution
{
public:string largestNumber(vector<int>& nums){// 全部转换为字符串int n = nums.size();vector<string> strs;strs.reserve(n);for (auto num : nums)strs.push_back(to_string(num));// 排序，如果ab>ba，就把a放在前面sort(strs.begin(), strs.end(), [](const string& str1, const string& str2){return str1 + str2 > str2 + str1;});// 拼接string ret;for (auto& str : strs)ret += str;return ret[0] == '0' ? "0" : ret;}
};这篇关于「贪心算法」最大数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
