LeetCode 179：最大数（贪心算法）—— 题解

欢迎阅读 欢迎来到「最大数」题解之旅本文将带你从“拼出最大的数字串”这一排序问题出发深入理解贪心 自定义排序的经典应用并掌握如何通过比较拼接结果来确定元素的排列顺序。在开始之前建议你先了解题目背景这是 LeetCode 179 题给定一组非负整数要求重新排列它们每个数不可拆分使组成的结果字符串字典序最大即数值最大。明确学习目标掌握如何将“最大数”问题转化为自定义排序问题理解比较器(a, b) - (ba).compareTo(ab)的含义和正确性并熟练处理前导零的特殊情况如[0,0]应输出0而非00。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [3,30,34,5,9]输出9534330。本文将从问题转化、排序规则设计、比较器实现、边界处理到代码实现层层递进。即使你对自定义排序还不熟悉我们也会从“两个数谁放前面更大”的直觉出发让你轻松抓住核心思想——不是比谁大而是比谁放前面拼出来更大。现在让我们一起重新排列数字拼出那个最大的整数吧 一、题目二、做题思路1. 问题分析前置分析给定一组非负整数重新排列它们的顺序每个数不可拆分使之组成一个最大的整数。本质是确定数字的排列顺序使得拼接后的字符串字典序尽可能大。2. 贪心策略核心决策规则将所有数字转换为字符串存入vectorstring。自定义排序规则对于任意两个字符串a和b若a b b a则a应排在b前面。排序后按此顺序拼接所有字符串得到的结果即为最大数。3. 正确性说明简单版本要使得拼接结果最大只需保证任意相邻的两个字符串都满足ab ba。这种比较关系具有传递性因此按此规则排序后整个序列的拼接结果一定是全局最优的。这是贪心选择性质的体现每次将当前“最适合”放在前面的字符串选出最终得到最优排列。4. 实现细节边界防护使用to_string将整数转为字符串。排序比较函数直接返回ab ba。拼接后若结果以0开头说明所有数字均为0直接返回0避免返回类似00的错误。5. 返回值目标映射返回拼接后的字符串ret即最大数的字符串表示。四、代码class Solution { public: string largestNumber(vectorint nums) { // 1. 将整数转换为字符串便于比较和拼接 vectorstring str; for (auto x : nums) { str.push_back(to_string(x)); } // 2. 自定义排序规则对于两个字符串 a 和 b // 如果 ab ba则 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定义比较规则 | | ┌──────────────────────────────────────────────┐ | | │ ① 若 ab ba → 称 a ba 排在 b 前 │ | | │ ② 若 ab ba → 称 a b顺序无所谓 │ | | │ ③ 若 ab ba → 称 a bb 排在 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] 中210 吗比较 210 与 102 | | 210 102所以 2 10故交换后 210 更大。 | ------------------------------------------------------ | v ------------------------------------------------------ | 推论最优排列必须无相邻逆序即所有相邻对满足 | | 前者 ≥ 后者按 规则。 | ------------------------------------------------------详细论证传递性是保证排序结果全局有序的基础。交换改进说明贪心操作的合理性如果发现相邻两个元素顺序不对即后面的“优于”前面的就交换它们交换后拼接结果一定变大。步骤 3归纳证明 —— 无逆序 ⇒ 全局最优文本示意图排序结果即为唯一最优text------------------------------------------------------ | 排序算法如快速排序按规则排好序得到序列 | | s₁, s₂, ..., sₙ满足对任意相邻 isᵢ ≥ 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对吗延伸挑战将问题改为“最小数”重新排列使拼接结果最小只需修改排序规则中的比较符号ab ba即可。动手试试并验证[3,30,34,5,9]的最小结果是否为3033459。如果将数字换成字符串数组要求拼接成最大字典序字符串规则相同。如果数组中有空字符串该如何处理如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨