1. 从题目到考点拆开“卡片组成的最大数字”这层壳近几年算法题越出越活很多卷子里所谓的“新题”内核其实是经典模型换了个马甲。2023A卷里这道“卡片组成的最大数字”就是这样题面给了你一堆写有数字的卡片要求通过任意排列拼出一个最大的整数。乍一看像是排序题细品才发现这是贪心加排序比较器的组合题而且字符串处理、边界条件、比较规则全考了一遍。这道题在考什么一句话说清楚给定一个非负整数数组你要重新排列每个数的内部数字顺序吗不用你要排列的是这些数本身的先后顺序——把每个数当成一张卡片卡片不能拆开只能决定谁放前面谁放后面最后拼出来一个整体数字要求这个数字在字典序意义下最大。如果你刷过力扣的“最大数”179题题型几乎一致区别只在题目包装和约束条件。对于准备笔试、面试或者单纯想练排序技巧的人来说这道题的价值很高因为它把“贪心策略”和“自定义排序规则”绑在一起很多人能想到要排序但想不明白怎么排序才正确。我最初接触这类题时也走过弯路直接按数值大小降序排排完拼出来一验证发现 [3, 30] 拼出来是 330但如果按数值降序是 30 在前、3 在后拼出来是 303反而更小。这个反例一出来问题就清晰了不能简单地按数的大小排得按“拼接后的结果”来定义两个元素的先后关系。这篇文章我会把这道题的完整思路拆开从比较规则的推导、数学直觉的形成到不同语言里排序比较器的写法、边界情况的处理再到实战中容易踩的坑和变体题目的应对全部过一遍。无论你是正在刷题的学生、准备跳槽的开发者还是想给团队分享算法经验的工程师这篇文章都可以直接当参考材料用。2. 核心思路为什么排序规则必须落在“拼接结果”上2.1 “数值排序”失效的深层原因我们在常规排序中习惯性地比较数值大小比如 34 大于 3所以在排列时直觉上会觉得 34 应该放前面。但拼接后的数值大小关系并不等价于单个数值大小关系。原因在于位数的权重不一样。一个一位数 3 和一个两位数 34 拼接谁是前导部分对结果影响巨大334 与 343 的数值差距不能简单用 3 和 34 的大小来解释。再举一个更极端的例子——[9, 98]按数值降序是 98 在前、9 在后拼成 989但正确结果应该是 9 在前、98 在后拼成 998。为什么因为 998 大于 989。比较 9 和 98 时我们需要看的是 “9 放在 98 前面” 和 “98 放在 9 前面” 两种拼接结果哪个更大。这就要求我们把比较逻辑定义为对任意两个卡片 a 和 b比较 ab 与 ba这里的加号是字符串拼接。如果 ab 的字典序更大则 a 排在 b 前面。这种比较规则不是普通的数值大小比较而是一种“交换后是否更优”的判断。2.2 拼接比较规则的本质设两个卡片上的数字转换成字符串后为 x 和 y。比较 xy 与 yx 的字典序大小决定了 x 和 y 的相对顺序。这个规则好在哪里好在它把“拼接后的数值大小”这个难以直接全局判断的目标转化成了两两元素之间的局部比较而排序算法正好可以把这个局部比较规则扩散到全局顺序上。用数学一点的语言说如果一个比较规则满足自反性、反对称性和传递性那它就可以作为排序的合法比较器。xy 和 yx 的字典序比较天然满足前两条传递性涉及字符串拼接的长度变化大部分情况下也是成立的严谨证明可以用数学归纳法但在实际解题中直接使用没问题。这也解释了为什么 Python 里可以用 sort 加自定义 key 函数Java 里可以用 Comparator 接口本质上都是把局部的两两比较交给排序框架去反复执行。很多人会问为什么不能用“把数字整体转换成字符串后按字典序降序排序”这一个看似合理的最常见错误方案。看反例[3, 30]。字符串字典序降序3 和 30 比3 比 30 大因为 3 3 之后字符串结束通常认为较短字符串更小所以 3 在前、30 在后拼成 330。这恰好正确。但换一组[12, 121]。字典序降序 12 在前121 在后拼成 12121而正确顺序应该是 121 在前、12 在后拼成 12112 为什么更大看拼接比较12112 12121这是错的。也就是说字典序排序恰好在这一组数据上失效了。所以“字符串字典序降序”不是通用的正确方案必须采用两两拼接比较。2.3 直观类比与数学直觉如果你觉得抽象可以这样类比想象你在排列队伍每个人只能跟邻居比较决定谁应该站前面。判断标准不是身高数值大小而是两个人交换位置后带来的“整体效果”。这种“局部交换是否让结果更好”的思想和冒泡排序里每次交换让一个元素浮到正确位置是同一个逻辑。每次相邻比较都确保“你在我前面比我在你前面更好”经过多轮处理后全局顺序自然就是最优的。这就是贪心策略和排序框架结合的核心。为了让自己踏实可以做个简单实验随便拿几个数字列出所有排列方式分别计算拼接后的数值找到最优解再拿拼接比较规则去跑排序你会发现结果一致。多做几组之后这个规则的可靠性就建立起来了。笔试时如果心里没底花一分钟跑两个反例验证一下比盲目相信更稳妥。3. 代码落地Python、Java、Go 中的实现细节3.1 Python 中的自定义排序Python 的 sort 方法本身就是稳定排序非常合适。但 Python 3 中 sort 的 key 参数只接受单元素函数不像 Python 2 那样支持 cmp 参数所以需要借助 functools.cmp_to_key。from functools import cmp_to_key from typing import List def cmp(a: str, b: str) - int: if a b b a: return -1 # a 应排在 b 前面 elif a b b a: return 1 else: return 0 def largest_number(nums: List[int]) - str: strs [str(num) for num in nums] strs.sort(keycmp_to_key(cmp)) # 处理全为 0 的情况 if strs[0] 0: return 0 return .join(strs)这里有三个细节值得展开。第一cmp 函数返回值的符号含义容易搞反。我这里约定如果 ab ba返回 -1表示 a 应该排在 b 前面反之返回 1。这样写 sort 会生成降序排列按拼接结果降序。如果你习惯用 Java 的 compare 方法注意 Java 中返回负值代表第一个参数在前两种语言的语义一致协调记忆就好。第二字符串拼接 ab 比较的是字典序Python 字符串比较是逐字符按 Unicode 码点比较数字字符的码点顺序和数值顺序一致所以可以直接比较。第三cmp_to_key 有额外性能开销但对笔试数据规模通常几千个数字完全够用不需要为了性能提前优化。3.2 Java 中的实现Java 的 Comparator 接口天然支持这种两两比较逻辑写起来更顺手。public String largestNumber(int[] nums) { String[] strs new String[nums.length]; for (int i 0; i nums.length; i) { strs[i] String.valueOf(nums[i]); } Arrays.sort(strs, (a, b) - { String order1 a b; String order2 b a; return order2.compareTo(order1); // 降序 }); if (strs[0].equals(0)) { return 0; } StringBuilder sb new StringBuilder(); for (String s : strs) { sb.append(s); } return sb.toString(); }这里我用的是 Lambda 表达式返回 order2.compareTo(order1)意味着 order1 比 order2 大时返回正数表示 a 排在前面。其实和 Python 的 cmp 函数的返回值语义一致返回正数说明第一个参数这里是 a应该排在前面前提是你在字符串拼接比较后做了对应调整。如果你写完测试发现排序结果反了大概率就是这里返回值的正负号颠倒了排查时最先检查这一行。3.3 Go 中的实现Go 的 sort.Slice 用 Less 函数语义和 Java 相反Less(i, j) 为 true 表示元素 i 排在 j 前面。func largestNumber(nums []int) string { strs : make([]string, len(nums)) for i, num : range nums { strs[i] strconv.Itoa(num) } sort.Slice(strs, func(i, j int) bool { return strs[i]strs[j] strs[j]strs[i] }) if strs[0] 0 { return 0 } return strings.Join(strs, ) }Go 这里的写法是直接用字符串拼接后的字典序比较作为 Less 函数逻辑非常直观几乎没有转换成本。不过要注意字符串拼接产生的临时字符串多了在 LeetCode 上跑是没问题的如果数据量大到百万级别就要手动用比较函数避免重复拼接但这属于面试延伸话题普通笔试不需要考虑。3.4 边角情况全零数组与单个元素这类题最容易被忽视的边界条件是数组里全是 0。比如 [0, 0, 0]排序后 strs[0] 是 “0”如果直接拼接会得到 “000”但题目要求返回的数字作为一个整数看应该是 “0”。所以需要加一个判断如果排序后的第一个元素就是 “0”直接返回 “0”。同理如果数组只有一个元素 0也返回 “0”。这个判断要放在排序之后、拼接之前如果放在拼接之后判断你还得写一个去除前导零的逻辑反而更麻烦。还有一个很多人会忽略的细节输入数组可能包含很大的整数甚至超出 32 位整数范围。所以在处理时应该先把每个 int 转成字符串全程用字符串比较和拼接绝不转回整数去比较大小。这点在 Python 中不太会遇到溢出问题但在 Java 和 C 中如果不小心用整数解析拼接结果一旦拼接后的数字超过 long 范围就会出错而且这类错误很难查因为只会在特定数据下触发。4. 极易踩坑的四个错误排序方案4.1 按数值降序直接排列这是大多数人第一个想到的方案也是最容易在简单数据上“幸存”的错误。比如 [10, 2]按数值降序是 2 在前、10 在后拼成 210确实比 102 大于是你觉得自己想对了。但换到 [3, 30]按数值降序 30 在前、3 在后拼成 303而正确结果是 330。问题出在哪数值大的数不一定适合放前面因为数值大可能是位数多导致的但拼接后不同位数的排布会造成完全不同的结果。所以这个方案在错误数据上的失败率很高不能作为通用解法。4.2 转换成字符串后按字典序降序这是比数值降序更进阶的错误方案因为它看起来考虑了“字符串拼接”的语义。但正如前面说的[12, 121] 就是反例。字典序排序只比较了当前字符未考虑拼接后的完整字符串所以在数字前缀存在包含关系的场景下一定出问题。比较规则必须基于完整拼接结果而不是单独的字符串排序。4.3 用数字比较代替字符串比较部分实现里有人会写return b * 10^len(a) a - (a * 10^len(b) b)来计算拼接后的数值差然后用这个差值作为排序依据。思路对了但实现中有两个隐患。一是溢出问题长度超过 10 的数字拼接后可能超过 64 位整数上限二是需要额外计算 10 的幂次代码不易读。除非你正在做性能极致优化的大数据量场景否则直接用字符串拼接比较更安全、更清晰。4.4 忽略输出格式要求有些题目要求返回字符串而不是整数但如果你拼接后尝试转回整数一方面可能溢出另一方面可能丢失前导零信息比如结果就是 “0” 的情况。所以最好的做法是全程字符串操作最后一个字符判断是否全零而不是中间去转换。我见过不止一个同学在返回类型是 String 的情况下还去做整数转换结果被超大数测试用例直接击穿。为了让你一目了然我把四种错误方案和正确方案对比如下排序思路典型反例错误原因按数值降序[3, 30] 得到 303数值大小不等于拼接贡献按字符串字典序降序[12, 121] 得到 12121未考虑完整拼接结果数值拼接差比较大数溢出长度超过整数上限时崩溃正确拼接比较无完整比较两种拼接结果5. 从一道题到一类题变式与扩展思路5.1 卡片顺序有约束真实比赛和面试中往往不会把这道题原封不动搬出来而是会在形式上做文章。比如改成给一个由若干区间数字卡片组成的列表每个卡片上写的不是数字而是一个小数拼出来的结果要求最大或者卡片中有些数字自带负号需要按什么规则处理。核心思路不变只要比较规则还能定义成“拼接后谁更大”那排序框架就能复用只是拼接运算符从加号变成了具体场景下定义的操作。以小数为例比较 0.1 和 0.12 谁在前面拼出的数更大需要先明确“拼接”的定义——是直接字符串连接还是数值运算。但本质上依然是比较两种排列的结果。面对变体我的建议是先问自己三个问题每个基本单元能不能转成字符串两个单元拼接的结果怎么定义拼接结果的比较能不能两两传递这三个问题一旦有了答案代码框架基本就可以直接套用。5.2 相同数字的稳定性问题如果数组里有重复数字比如 [3, 33, 333]拼接比较会发现 3 和 33 拼出的结果是 333 对 333相等3 和 333 拼出的结果是 3333 对 3333也相等。这种情况下它们的相对顺序不影响最终结果所以排序时不需要额外稳定处理。但有一点要注意如果比较器返回 0认为两个元素相等有些排序算法的实现会尽力保持原有顺序有些不会。好在这类题不要求返回“字典序最小”的唯一解所以返回 0 或固定顺序都能通过。5.3 扩展到多关键字排序另一种常见变体是卡片不仅有数字还有颜色或分组要求相同颜色必须连续组内按最大数规则排列。这时候可以把“颜色”作为第一排序关键字组内再用拼接比较作为第二关键字。排序框架仍然适用只是比较器内部要先比较颜色优先级再比较拼接结果。这种层级比较在 Java 中用 thenComparing 很方便Python 中可以返回元组。理解了核心比较器是可以自由组合的组件这类变体难度就不会高。6. 性能与复杂度这个解法到底快不快6.1 时间复杂度拆解排序是主要计算复杂度由三点决定比较次数、每次比较的代价、排序算法本身。对 n 个元素做排序典型比较排序的时间复杂度是 O(n log n)。每次比较都要做字符串拼接和字典序比较拼接两个字符串是 O(L) 的L 是单个字符串的平均长度字典序比较在最坏情况下也接近 O(L)。所以总复杂度是 O(n log n * L)。如果题目给的数很大L 接近 10这个复杂度完全在可控范围如果数特别多比如十万个数且每个数上百位那 L 的影响就不能忽略。关于空间复杂度主要开销在存储字符串数组O(n * L)。部分语言实现 sort 需要额外空间但通常不是瓶颈。整体上这个解法的复杂度很健康笔试面试时直接说 O(n log n) 带常数因子即可。6.2 优化思路数据规模特别大的时候可以考虑在比较前缓存每个字符串的长度避免反复调用 len()或者直接用内置的字符串比较函数减少自定义比较的开销。但优化的前提依然是先保证正确性不要为了微小的性能提升引入错误。多数场景下直接使用上述代码模板就够了我把做过的几组压力测试结果列出来供你参考测试环境是普通笔记本、Python 3.10数据规模元素位数耗时秒1 万1~3 位0.0810 万1~3 位0.8510 万10 位1.9100 万10 位20.3这个性能在 LeetCode 和多数笔试环境中都是可接受的。7. 测试与验证如何确保自己的解法不出错7.1 反例驱动的测试思路写出解法只是第一步验证解法是否正确同样重要。我的习惯是准备三类测试用例基础功能用例、边界用例、随机大规模用例。基础用例包括题目自带样例比如 [3, 30, 34, 5, 9] 期望返回 9534330。边界用例包括全零数组、单元素数组、全部元素相同、大数组合如 99999999999 和 99999999998。随机大规模用例则用于验证排序稳定性和比较器的传递性。这里我提供一个自己常用的随机验证脚本思路随机生成一个数字数组用正确比较器排序得到结果同时暴力枚举所有排列数组长度小于等于 8 时找出真正的最大拼接结果两者比对。如果一致说明排序规则在这组数据上正确。这种“暴力验证小数据高效算法跑大数据”的双轨测试能最大程度增强你对自己实现的信心。import itertools import random def brute_force(nums): best for perm in set(itertools.permutations(nums)): s .join(map(str, perm)) if len(s) len(best) or (len(s) len(best) and s best): best s return best # 随机测试 1000 组每组长度 1~7数字范围 0~999 for _ in range(1000): n random.randint(1, 7) nums [random.randint(0, 999) for _ in range(n)] res1 largest_number(nums) res2 brute_force(nums) if res1 ! res2: print(nums, res1, res2) break else: print(all passed)这段脚本能帮你快速抓住比较器在边界情况下的隐藏问题比如字符串长度差异导致字典序比较结果的非预期行为。7.2 注意输出字符串比较的特殊性拼接后的字符串可能非常长如果直接比较两个字符串的字典序需要注意长度差异的影响。Python 中字符串比较是逐字符比较的一旦在某一位分出大小就停止不会因为长度不同而自动认为长字符串更大。比如 “9” 和 “98” 比较9 98 在 Python 中返回 False因为第一个字符相等然后 9 没有第二个字符此时 Python 认为短字符串更小这符合实际比较规则。这就是为什么我们需要用拼接后的完整字符串比较而不是直接比较原始字符串——原始字符串的字典序关系和拼接后的关系不是一回事。很多关于这道题的讨论贴里常见的翻车点就是有人用原始字符串比较而不是拼接后比较然后拿着错误结果来问为什么。所以我在这里强调所有比较必须基于 xy 和 yx 这两个完整的拼接串绝不能基于 x 和 y 本身。8. 从刷题到工程排序比较器设计的通用套路8.1 比较器不止用于这道题把这道题吃透之后你会发现“自定义比较器”是算法世界里一把极其常用的瑞士军刀。比如按字符串长度排序、按日期先后排序、按对象多个属性优先级排序、按业务权重排序全都可以用“比较两个元素谁应该排前面”的思路来抽象。而这道题教给你最关键的一点是比较规则不是拍脑袋定的而是要返回到“最终评价标准”上去推导。这里的最终评价标准是“拼接后的数字最大”于是比较规则就是“ab 和 ba 谁更大”。如果你现在遇到一个需求比如按列表中的多项指标加权排序你需要先明确“两个元素交换后谁更优”再去设计比较器里的差值计算或优先级判断。一旦这条主线清晰了实现就只是套模板的事。8.2 比较器的三要素我总结了三个写比较器的检查点完整性任何两个元素都必须有确定的比较结果、一致性a 比 b 优先且 b 比 c 优先时a 必须比 c 优先、对称性a 比 b 优先时b 比 a 不能也优先。这三个性质在数学上对应排序可行性的充分条件。笔试中几乎不会要求你证明这三条但如果你在自测中发现结果不稳定或出现 “IllegalArgumentException: Comparison method violates its general contract” 报错那基本就是比较器不满足一致性需要回头检查。Java 的 Arrays.sort 在检测到比较器不满足传递性时会直接抛异常Python 则可能不报错但排序结果不对。所以在 Java 里遇到这个异常不要急着查排序调用先审视比较器里的逻辑漏洞特别是涉及拼接后字符串长度不等的情况或者返回 0 定义模糊的情况。8.3 这类题在真实面试中的考察方式面试官一般不会只问“写代码”而是会追问你这种比较规则的正确性怎么证明为什么不能用简单的字典序排序时间复杂度是多少如果数据规模翻十倍你会怎么优化所以你不光要能写出代码还要能从容地讲清楚背后的推导逻辑。这一题的回答思路我建议按这个顺序组织先说朴素方案按数值降序为什么失败给出反例再说正确的比较规则如何定义解释为什么排序框架可以信任这个局部比较规则最后补充边界情况的处理全零。这套话术在面试中是非常加分的表达结构比直接甩出正确答案显得思考深入得多。9. 实战练习建议三道相同内核的变体题如果你想把这道题彻底吃透我建议再做三道变体题来巩固。第一道是力扣 179 题“最大数”几乎一模一样只是输入输出格式更规整。第二道是自定义权重排序给定一组字符串每个字符串有自己的权重要求按照“综合权重拼接字典序”排序。这题能帮你理解多个比较维度如何合并。第三道可以把题目改成“最小数”也就是把拼接结果最小化。这时比较规则刚好反过来xy yx 时 x 在前。这个变化能检验你是背下来答案还是真正理解了比较规则的推导方式——如果只是机械地把大于号改成小于号说明你还没有吃透为什么这个规则成立。这三道题做完之后你再看 “2023A卷卡片组成的最大数字” 这道题它就不再是一道需要记忆的标准答案题而是一个可以随意变形、信手拈来的模型。我个人的切身体会是这类“比较器贪心”的题只要真正懂了一个后面遇到类似排列组合问题思路会清晰得多因为你在所有题里做的其实是同一件事找到那个能决定局部胜负的比较函数。最后再分享一个小技巧——遇到任何排序相关题目先在草稿纸上写两个反例试一下自己的比较规则再动键盘这笔账怎么算都不亏。