1. 从一道题到一类题理解“最大数”问题的本质最近在备赛蓝桥杯国赛刷题时又遇到了“最大数”这个经典问题。乍一看题目描述很简单给定一组非负整数重新排列它们的顺序使其连接起来构成一个最大的整数。比如给你[3, 30, 34, 5, 9]你应该输出9534330。很多刚接触的朋友可能会想这不就是按数字的字典序从大到小排个序吗把数字转成字符串然后sorted(arr, keystr, reverseTrue)不就完事了如果你真这么做了面对[3, 30]这个例子你会得到303但正确答案其实是330。这个“坑”几乎每个认真刷过这道题的人都踩过它完美地诠释了算法竞赛中“想当然”的代价。这道题之所以经典是因为它考察的远不止排序本身。它要求你深入理解自定义比较规则思考字符串拼接的数学本质并能在不同编程语言中优雅地实现。更重要的是它是一类“构造最优序列”问题的代表其解题思路可以迁移到许多其他场景比如任务调度、资源分配等。备战国赛我们需要的不只是AC一道题而是掌握其背后的思想做到举一反三。接下来我将从问题本质、核心解法、代码实现细节以及相关的变体问题全方位拆解这个“最大数”问题希望能帮你彻底吃透它。2. 为什么简单的字典序排序会失败我们首先需要彻底弄清楚为什么直觉上的“字典序降序”策略会出错。问题的核心在于我们比较的不是单个字符串a和b的字典序而是由它们拼接而成的两个字符串ab和ba的字典序。2.1 一个反直觉的案例剖析以a3,b30为例。如果直接比较字符串3和30的字典序330因为第一个字符相同比较第二个字符时3已结束而30还有0在字符串比较中较短的字符串如果在前面部分相同则被视为更小等等这里需要仔细说清楚因为这是一个常见的混淆点。实际上在大多数编程语言的字典序比较中比较是从左到右逐个字符进行。比较3和30第一个字符都是3相等。接下来看第二个字符。3没有第二个字符长度为1而30的第二个字符是0。当一个字符串是另一个字符串的前缀时较短的字符串通常被视为更小在Python中确实如此。所以330。 因此按字符串降序排列30会排在3前面得到序列[30, 3]拼接为303。但我们的目标是拼接后的数字最大。让我们比较两种拼接方式ab即330 330ba即303 303显然330303。所以为了得到最大的拼接结果3应该排在30前面。这个例子清晰地表明决定两个元素a和b谁该在前、谁该在后的依据不是a和b本身的大小而是ab和ba这两个拼接结果的大小比较。如果abba那么a就应该排在b的前面。2.2 自定义比较规则的数学基础为什么比较ab和ba是合理的这背后其实隐含着一种“传递性”的假设以确保排序结果的一致性。我们需要证明如果对于任意三个字符串a, b, c定义a“优于”b当且仅当ab ba那么这种“优于”关系在满足一定条件时可以构成一个全序关系从而使得排序算法能正常工作。严格证明需要用到数学归纳法和反证法但我们可以从直觉上理解我们的目标是最大化最终拼接字符串。假设我们已经有了一个最优排列那么在这个排列中任意相邻的两个元素x和y都必须满足xy yx。否则交换它们就能得到一个更大的数与“最优”矛盾。因此一个全局最优的排列其局部任意相邻对都必须满足这个比较规则。而基于这个规则进行排序正是试图构造一个满足所有相邻对都满足该规则的序列这通常就能得到全局最优解对于非负整数输入该规则满足传递性排序结果是唯一的。注意这里有一个极其关键的边界情况——前导零。如果排序后最大的数字是0例如输入为[0, 0]那么拼接结果应该是0而不是00。在代码实现中排序后我们需要检查结果的第一个字符如果是0则直接返回0。3. 核心解法实现跨越语言差异的优雅排序理解了比较规则实现就变得直接了。核心就是自定义排序的比较器Comparator。不同编程语言的实现方式各有特色但思想相通。3.1 Python实现利用functools.cmp_to_keyPython的sorted()函数默认不支持老式的cmp函数但我们可以使用functools.cmp_to_key将比较函数转换为键函数。from functools import cmp_to_key class Solution: def largestNumber(self, nums): # 第一步将数字转换为字符串避免后续频繁转换 str_nums list(map(str, nums)) # 第二步定义比较函数 def compare(x, y): # 如果 xy yx则 x 应该排在 y 前面返回负数 # 如果 xy yx则 y 应该排在 x 前面返回正数 # 如果相等返回0 if x y y x: return -1 # x 在前 elif x y y x: return 1 # y 在前 else: return 0 # 第三步使用自定义比较器排序 str_nums.sort(keycmp_to_key(compare)) # 第四步处理前导零 # 排序后最大的元素会在最前面。如果它是0说明所有元素都是0 result .join(str_nums) return result if result[0] ! 0 else 0为什么这样写比较函数在Python的sort中key函数期望的规则是如果希望x排在y前面比较函数应返回一个负数如果希望y排在x前面则返回正数相等返回0。这与C/C、Java中的Comparator约定是一致的。记住口诀“前减后”得到负数则前一个参数排前面。在我们的compare(x, y)中当xy yx时我们希望x在前所以返回-1。3.2 Java实现实现Comparator接口Java中通常通过实现ComparatorString接口并重写compare方法来实现。import java.util.Arrays; import java.util.Comparator; class Solution { public String largestNumber(int[] nums) { // 转换为字符串数组 String[] strNums new String[nums.length]; for (int i 0; i nums.length; i) { strNums[i] String.valueOf(nums[i]); } // 定义比较器 ComparatorString comparator new ComparatorString() { Override public int compare(String a, String b) { String order1 a b; String order2 b a; // 注意这里是降序排列所以用 order2.compareTo(order1) return order2.compareTo(order1); } }; // 排序 Arrays.sort(strNums, comparator); // 处理前导零 if (strNums[0].equals(0)) { return 0; } // 拼接结果 StringBuilder sb new StringBuilder(); for (String num : strNums) { sb.append(num); } return sb.toString(); } }Java比较器的细节Arrays.sort(strNums, comparator)会按照comparator定义的顺序排序。在compare(a, b)方法中如果返回负数表示a应该排在b之前。我们想要的是ab较大的组合中a在前。因为order1 ab,order2 ba如果order1更大即ab ba我们希望a在前此时应该返回负数。但注意字符串的compareTo方法如果order1大于order2会返回正数。所以为了得到我们想要的排序ab大的在前我们实际比较的是order2.compareTo(order1)。当ab ba时order1 order2那么order2.compareTo(order1)返回负数恰好表示a应该排在b前面。这一点需要仔细捋清逻辑。3.3 C实现使用lambda表达式与sortC的实现非常简洁可以利用std::sort和lambda表达式。#include string #include vector #include algorithm using namespace std; class Solution { public: string largestNumber(vectorint nums) { vectorstring strNums; for (int num : nums) { strNums.push_back(to_string(num)); } // 定义排序规则如果 ab ba则 a 排在 b 前面 sort(strNums.begin(), strNums.end(), [](const string a, const string b) { return a b b a; // 注意这里是大于号满足条件则a在前 }); // 处理前导零 if (strNums[0] 0) { return 0; } // 拼接结果 string result; for (const string s : strNums) { result s; } return result; } };C排序的陷阱std::sort要求比较函数是严格弱序。我们的规则ab ba是否满足严格弱序对于非负整数转换的字符串是满足的。但必须注意我们不能写成ab ba因为sort要求比较函数对于相等的元素返回false否则可能导致未定义行为。在我们的场景中如果ab ba谁在前都无所谓所以返回false是安全的即ab ba不成立。sort的第三个参数是一个返回bool的谓词当返回true时表示第一个参数应该排在第二个参数之前。所以return ab ba;完全符合我们的需求。4. 时间复杂度分析与优化思考一个常见的疑问是在比较函数中每次都进行字符串拼接ab和ba会不会导致性能问题我们需要分析一下时间复杂度。假设有n个数字平均字符串长度为k。排序算法如快速排序的时间复杂度为O(n log n)。每次比较需要拼接两个字符串并比较拼接操作的时间复杂度为O(k)比较操作也是O(k)。因此总的时间复杂度为O(n log n * k)。由于k是数字的位数对于32位整数k最大为10对应2147483647可以视为常数。所以整体复杂度可以近似为O(n log n)这在n达到10^5数量级时也是可以接受的。有没有优化空间有的。一种思路是避免在每次比较时都创建新的字符串。我们可以预先计算所有数字的字符串形式然后在比较时直接比较两个字符串指针指向的字符模拟拼接过程而无需物理拼接。但这会使得比较函数复杂很多代码可读性下降。在竞赛和面试中直接使用拼接比较的方法是最清晰、最不容易出错的做法除非性能测试表明这里确实是瓶颈在常规数据规模下几乎不会否则不建议进行这种微优化。另一个优化点是处理全零数组。我们可以在排序后检查结果字符串的第一个字符。但更激进一点我们可以在排序前先判断如果数组中的最大值是0那么可以直接返回0。因为只要有一个数大于0它排序后必然会出现在最前面除非有更特殊的规则但本题中非负整数大于0的数其字符串表示肯定以非0开头。这个优化可以节省排序开销但代码需要额外遍历一次数组。5. 举一反三相关变体问题与解题思路掌握了“最大数”的基本解法我们可以看看它的几种变体这能帮助我们深化理解。5.1 变体一构造最小数问题给定一组非负整数重新排列使其拼接成最小的数。 解法核心比较规则反转即可。我们希望a在b前面当且仅当abba。排序后同样需要处理前导零问题。但这里有个微妙之处如果结果有前导零比如0123我们应该将其转化为123吗不因为0123在数值上等于123但作为字符串0123就是最小的拼接结果。通常题目会要求输出字符串所以直接返回拼接后的字符串即可除非特别说明要输出去掉前导零的数值。5.2 变体二带有负数的最大数问题给定一组整数可能包含负数重新排列使其拼接成的数最大。 解法这变得复杂了。因为负号-的引入破坏了字符串拼接比较的简单性。例如-12和3-123 -1233-12 3-12后者看起来更大但我们需要比较的是数值还是字符串通常这类问题会明确规则。一种可能的策略是分组正数一组负数一组。正数内部按原“最大数”规则排序大数在前。负数内部呢对于负数我们希望其绝对值小的排在前面吗不一定。例如-1和-12-1-12 -1-12-12-1 -12-1哪个数值更大这需要定义清晰的比较规则可能需要对负数字符串进行特殊处理比如比较时去掉负号但顺序要反转。这类变体在竞赛中不常见但思考它能锻炼对问题规则的抽象能力。5.3 变体三最大数之删除K位数字问题给定一个以字符串表示的非负整数num和一个整数k移除k位数字使得剩下的数字最小。 这是LeetCode上的一道经典题402. Remove K Digits。虽然目标是最小化但思路与“最大数”的排序思想有异曲同工之妙。其核心是贪心算法为了使得剩下的数字最小我们应该尽可能让高位的数字小。因此我们可以用一个栈来维护结果遍历字符串对于每个数字如果栈非空、栈顶数字比当前数字大、并且还有删除次数k0那么就弹出栈顶相当于删除这个数字。最后如果k还有剩余则从末尾删除因为此时栈内数字是递增的末尾最大。这个“栈顶比当前大则弹出”的动作其实隐含了一种局部比较和选择与“最大数”中比较相邻两个元素拼接大小的思想类似都是基于局部最优希望得到全局最优。6. 备赛实战如何将此类题目做对、做快、做稳在国赛级别的竞赛中遇到这类题目目标不仅仅是AC还要追求快速、稳健地写出代码。以下是我总结的几点实战经验1. 快速识别题型看到“重新排列数字组成最大/小数”、“拼接”等关键词立刻联想到自定义排序比较规则是ab与ba。这是第一步也是最关键的一步能节省大量走弯路的时间。2. 默写比较器模板对于不同语言提前准备好比较器的写法。比如Python的cmp_to_keyJava的匿名ComparatorC的lambda表达式。在练习时形成肌肉记忆比赛时就能信手拈来。3. 牢记边界条件全零数组排序后结果第一个字符是0直接返回0。这是一个非常高频的考点几乎每次都要检查。大数输入虽然题目通常说输出字符串但有些变体可能要求输出整数。要注意结果可能非常大远超long long范围必须用字符串处理。输入为空数组根据题目要求处理通常返回空字符串或0。4. 测试用例设计自己编写测试用例是保证代码正确的关键。针对此题我建议至少测试以下几组常规用例[3,30,34,5,9]-9534330包含重复数字[1, 1, 1]-111导致字典序陷阱的用例[3, 30]-330[10, 2]-210210102全零用例[0, 0, 0]-0单个数字[1]-1大数[999999991, 9]-9999999991注意拼接后的比较5. 调试技巧如果在比赛中提交后WA错误答案首先检查前导零处理。如果还不对可以尝试打印排序后的中间结果字符串数组看看顺序是否符合预期。例如对于[3,30,34]排序后的数组应该是[34, 3, 30]因为343 334,330 303,3430 3034这里需要仔细验证实际上343343,334334, 所以34在3前330330,303303, 所以3在30前。最终顺序[34, 3, 30]拼接为34330。通过中间输出可以快速定位是比较器逻辑错误还是其他问题。7. 从算法到思想贪心与排序的深度关联“最大数”问题本质是一个贪心算法问题。我们采取的“对于任意两个元素如果ab ba则把a放前面”的策略就是一种贪心选择。我们相信通过这种局部两两比较的规则进行排序得到的全局序列就是最优的。这需要证明其贪心选择性质和最优子结构。很多字符串拼接、安排顺序以求最优值的问题最终都归结为定义一个合适的“比较规则”然后排序。例如任务调度有若干任务每个任务有处理时间和截止时间如何安排顺序使超时任务最少可能需要比较任务的处理时间和截止时间。哈夫曼编码合并果子问题每次选择最小的两堆合并这实际上也是一种基于优先队列可以看作动态排序的贪心。这种“定义排序规则”的思想非常强大。它告诉我们面对一个看似复杂的序列安排问题不妨先思考如果只考虑两个元素谁应该排在前面把这个规则想清楚然后用排序来实现往往就能得到正确答案。在备赛过程中多积累这类“排序贪心”的模型非常有益。下次遇到类似“重新排列以最大化/最小化某个指标”的问题时先尝试设计两两之间的比较规则这可能是打开解题大门的钥匙。最后关于这道题我个人在多次编写中最大的体会是边界条件往往比核心算法更考验人。我曾在一次比赛中因为忘记处理全零情况而丢分。所以现在每次写完排序逻辑我的手指会不自觉地立刻敲上处理前导零的那几行代码这已经成了一种条件反射。在高压的竞赛环境中这种由经验固化下来的“肌肉记忆”是稳定发挥的重要保障。希望这篇详细的拆解能帮你不仅搞定这一道题更能掌握这一类题在国赛中遇到时能从容应对。