[LeetCode]179. 最大数

问题

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

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

示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"
示例 3：
输入：nums = [1]
输出："1"
示例 4：
输入：nums = [10]
输出："10"

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 10的九次方

思路及代码

对于 nums 中的任意两个值 a 和 b，我们无法直接从常规角度上确定其大小/先后关系。

但我们可以根据「结果」来决定 a 和 b 的排序关系：

如果拼接结果 ab 要比 ba 好，那么我们会认为 a 应该放在 b 前面。

这是一种贪心的思想，可以证明，该贪心策略能取到全局最优解。

假设存在一个最优序列不满足该排序规则，那么必然存在至少一对相邻数字 a 与 b，我们将 a 与 b 交换后新序列的值必然增加，与假设矛盾。因此，满足该排序规则是该序列最优的充分条件。

这里证明从略，因为做没做过这题的人几乎都无法在面试中给出严格证明。

代码如下：

#include<bits/stdc++.h>
using namespace std;
class Solution {
	public:
		static bool cmp(string a, string b) {//不加static会报错
			return a + b > b + a;
		}
		string largestNumber(vector<int>& nums) {
			vector<string> str;
			for (int i : nums) {
				str.push_back(to_string(i));//将容器vectors中的元素都变为字符串加入到str容器中
			}
			sort(str.begin(), str.end(), cmp);
			string ans;
			if (str[0] == "0") {
				ans = "0";
			} else {
				for (string i : str) {
					ans += i;
				}
			}
			return ans;
		}
};

int main() {
	Solution s;
	vector<int> nums = {3, 30, 34, 5, 9};
	cout << s.largestNumber(nums) << endl;
}

结论：看到要求两个整数 x,y 如何拼接得到结果更大时，就想到先转字符串，然后比较 x+y 和 y+x。这是经验。

n个整数也是如此，因为可以证明当其局部满足该条件（拼接结果最大）时，整体也满足该条件。

[LeetCode]179. 最大数

原文：https://www.cnblogs.com/p0lar1s/p/14649367.html