力扣题解（最大数）

排序179. 最大数

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

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

思路：

对数组重新排列，使得按照题目所要求的顺序输出。

排序规则：对于数组中的数a和数b，若ab>ba，则a在前，b在后。

正确性：若ab>ba,则acb>bca，保证了将任何数放ab之间，不改变大小关系。

因此按照上述做法得出的序列是x1,x2,x3.....,最优解是y1,y2,y3.....,假设前i-1个一样，则xi！=yi，假设xi==yj，则必有yiyj<yjyi，且对于处于i到j之间的数字组合z，yizyj<yjzyi，因此换i，j位置会大于等于未换位置的最优解，但是最优解是最大值，因此换后仍是最大值。因此贪心得到的是最优解。

class Solution {
public:
 
	struct cmp2 {
 
							void getarr(vector<int>& p, int a)
							{
								int i = 0;
								while (a != 0)
								{
									int b = a % 10;
									p.push_back(b);
									a /= 10;
								}
								reverse(p.begin(), p.end());
							}
 
							bool operator () (int& p1, int& p2) //p1前，p2后
							{
                               if(p1==p2)
                               return false;
								if (p1 == 0)
									return true;
								else if (p2 == 0)
									return false;
								vector<int>q1;
								vector<int>q2;
								getarr(q2, p2);
								getarr(q1, p1);
                                double tt=0;
                                for(int i=0;i<q1.size();i++)
                                {  
                                    tt=tt*10+q1[i];
                                }
                                for(int i=0;i<q2.size();i++)
                                {  
                                    tt=tt*10+q2[i];
                                }
                                 double tt2=0;
                                for(int i=0;i<q2.size();i++)
                                {  
                                    tt2=tt2*10+q2[i];
                                }
                                for(int i=0;i<q1.size();i++)
                                {  
                                    tt2=tt2*10+q1[i];
                                }
			                    return tt2>tt;
							};
 
 
						};
						string largestNumber(vector<int>& nums) {
 
							priority_queue<int, vector<int>, cmp2>dp;
                            int flag=0;
							for (auto e : nums)
							{
								dp.push(e);
                                if(e!=0)
                                flag=1;
							}
                            
							string ret;
                            if(flag==0)
                            return "0";
							for (int i = 0; i < nums.size(); i++)
							{
								int a = dp.top();
								dp.pop();
								ret += to_string(a);
							}
                            
							return ret;
 
						}
};