企业官网建设流程全解析

👋 欢迎阅读

🎯 欢迎来到「最大数」题解之旅！本文将带你从“拼出最大的数字串”这一排序问题出发，深入理解贪心 + 自定义排序的经典应用，并掌握如何通过比较拼接结果来确定元素的排列顺序。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 179 题，给定一组非负整数，要求重新排列它们（每个数不可拆分），使组成的结果字符串字典序最大（即数值最大）。

• 明确学习目标：掌握如何将“最大数”问题转化为自定义排序问题，理解比较器(a, b) -> (b+a).compareTo(a+b)的含义和正确性，并熟练处理前导零的特殊情况（如[0,0]应输出"0"而非"00"）。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如nums = [3,30,34,5,9]输出"9534330"）。

本文将从问题转化、排序规则设计、比较器实现、边界处理到代码实现，层层递进。即使你对自定义排序还不熟悉，我们也会从“两个数谁放前面更大”的直觉出发，让你轻松抓住核心思想——不是比谁大，而是比谁放前面拼出来更大。现在，让我们一起重新排列数字，拼出那个最大的整数吧！ 🔢📊

一、题目

二、做题思路

1. 问题分析（前置分析）

给定一组非负整数，重新排列它们的顺序（每个数不可拆分）使之组成一个最大的整数。本质是确定数字的排列顺序，使得拼接后的字符串字典序尽可能大。

2. 贪心策略（核心决策规则）

• 将所有数字转换为字符串，存入vector<string>。

• 自定义排序规则：对于任意两个字符串a和b，若a + b > b + a，则a应排在b前面。

• 排序后，按此顺序拼接所有字符串，得到的结果即为最大数。

3. 正确性说明（简单版本）

要使得拼接结果最大，只需保证任意相邻的两个字符串都满足a+b > b+a。这种比较关系具有传递性，因此按此规则排序后，整个序列的拼接结果一定是全局最优的。这是贪心选择性质的体现：每次将当前“最适合”放在前面的字符串选出，最终得到最优排列。

4. 实现细节（边界防护）

• 使用to_string将整数转为字符串。

• 排序比较函数直接返回a+b > b+a。

• 拼接后若结果以'0'开头，说明所有数字均为0，直接返回"0"（避免返回类似"00"的错误）。

5. 返回值（目标映射）

返回拼接后的字符串ret，即最大数的字符串表示。

四、代码

class Solution { public: string largestNumber(vector<int>& nums) { // 1. 将整数转换为字符串，便于比较和拼接 vector<string> str; for (auto x : nums) { str.push_back(to_string(x)); } // 2. 自定义排序规则：对于两个字符串 a 和 b， // 如果 a+b > b+a，则 a 应排在 b 前面， // 这样拼接后的整体数字最大。 sort(str.begin(), str.end(), [](const string& a, const string& b) { return a + b > b + a; }); // 3. 拼接排序后的字符串 string ret; for (auto& s : str) { ret += s; } // 4. 处理特殊情况：如果排序后第一个字符是 '0'， // 说明所有数字都是 0（因为最大的数字为0），直接返回 "0" if (ret[0] == '0') { return "0"; } return ret; } };

五、流程图

六、正确性说明（详细版）

步骤 1：符号与问题建模

+--------------------------------------------------+ | 输入数组 nums，转为字符串 | | 对任意两个字符串 a, b，定义比较规则： | | ┌──────────────────────────────────────────────┐ | | │ ① 若 a+b > b+a → 称 a > b，a 排在 b 前 │ | | │ ② 若 a+b = b+a → 称 a = b，顺序无所谓 │ | | │ ③ 若 a+b < b+a → 称 a < b，b 排在 a 前 │ | | └──────────────────────────────────────────────┘ | | 贪心策略：按该规则对数组进行降序排序。 | | 贪心实质：每一步比较两个相邻元素， | | 若逆序则交换，最终使任意相邻对满足前者 ≥ 后者。 | +--------------------------------------------------+

• 贪心思想：要得到最大拼接数，局部最优就是对于任意两个字符串，让ab > ba的那个放前面，因为这样拼接后整体更大。通过反复交换逆序对（类似冒泡排序），最终全局最优。

步骤 2：关键性质 —— 传递性与交换改进

+------------------------------------------------------+ | 传递性（核心性质）： | | 若 a > b 且 b > c，即 ab > ba 且 bc > cb， | | 则必有 a > c，即 ac > ca。 | | 理由：字符串拼接的比较满足传递性（可严格证明）。 | | +------------------------------------------------------+ | v +------------------------------------------------------+ | 交换改进（贪心操作）： | | 若排列中存在相邻逆序 ... x y ... 且 y > x， | | 则交换为 ... y x ... 后，整体拼接字符串严格变大。 | | 证明：前缀和后缀不变，只比较 xy 与 yx， | | 而 y > x ⇒ yx > xy，故新串 > 原串。 | | 示例：[10, 2] 中，2>10 吗？比较 210 与 102， | | 210 > 102，所以 2 > 10，故交换后 "210" 更大。 | +------------------------------------------------------+ | v +------------------------------------------------------+ | 推论：最优排列必须无相邻逆序，即所有相邻对满足 | | 前者 ≥ 后者（按 > 规则）。 | +------------------------------------------------------+

详细论证：

• 传递性是保证排序结果全局有序的基础。

• 交换改进说明贪心操作的合理性：如果发现相邻两个元素顺序不对（即后面的“优于”前面的），就交换它们，交换后拼接结果一定变大。

步骤 3：归纳证明 —— 无逆序 ⇒ 全局最优

文本示意图：排序结果即为唯一最优

text

+------------------------------------------------------+ | 排序算法（如快速排序）按规则排好序，得到序列： | | s₁, s₂, ..., sₙ，满足对任意相邻 i，sᵢ ≥ sᵢ₊₁。 | | 由传递性，对任意 i < j，也有 sᵢ ≥ sⱼ。 | | 即整个序列按该序严格降序。 | +------------------------------------------------------+ | v +------------------------------------------------------+ | 假设存在另一个最优排列，它也必须无相邻逆序。 | | 由于该序关系是传递且完全的（任意两元素可比）， | | 满足全序降序的排列是唯一的（除相等元素可互换）。 | | 相等元素互换不改变拼接结果。 | | 因此，该排列与排序结果拼接后完全一样。 | +------------------------------------------------------+ | v +------------------------------------------------------+ | 结论：贪心排序得到的字符串即为最大整数。 | +------------------------------------------------------+

详细论证：

• 排序算法通过反复应用“交换逆序”的贪心操作（类似于选择排序或快速排序），最终得到一个无相邻逆序的排列。

• 由传递性，无相邻逆序意味着全局有序，即对于任意前面的元素sᵢ和后面的元素sⱼ，都有sᵢ ≥ sⱼ。

• 若存在另一最优排列，则它也必须无相邻逆序（否则可通过交换改进），而全序关系迫使其与排序结果一致（仅相等元素可变，但不影响拼接结果）。

• 因此，贪心排序的结果就是最大拼接整数。

🎯 闭幕

🎉 恭喜你完成了「最大数」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 如果直接按数值大小降序排序（如[9, 80]会排成[9, 80]得到980，正确；但[3, 30]会排成[30, 3]得到303，而最优是330），这说明简单降序为何会失败？

• 代码最后检查ret[0] == '0'时返回"0"。如果数组中有多个0（如[0, 0]），排序后ret会是"00"，此时ret[0]=='0'成立并返回"0"，这符合预期。但如果数组中有[0, 0, 1]，排序后第一个字符是'1'，不会触发，返回"100"，对吗？

📚延伸挑战

• 将问题改为“最小数”（重新排列使拼接结果最小），只需修改排序规则中的比较符号（a+b < b+a）即可。动手试试，并验证[3,30,34,5,9]的最小结果是否为3033459。

• 如果将数字换成字符串数组，要求拼接成最大字典序字符串，规则相同。如果数组中有空字符串""，该如何处理？

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏
👤 关注作者，获取更多题解
💬 留言交流你的疑问或优化思路

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨