最大数 图解题解
这道题到底在问什么
- 输入
- nums = [3,30,34,5,9]
- 输出
- "9534330"
最优解：一步一步想明白
- 3记住这条比较规则：a 在 b 前 ⇔ 拼接 a+b 比 b+a 大。下面用冒泡排序一对一对地套用它。
- 4初始数组就是题目给的顺序，还没排。我们用冒泡排序，从左到右一对一对比较相邻两个数。
- 5比较相邻的 3 和 30：拼成 "330" 和 "303"，前者大，3 该排在前，不动。
- 6比较相邻的 30 和 34：拼成 "3034" 和 "3430"，后者大，说明 34 该排在前，要交换。
- 7因为 "3430" 比 "3034" 大，把 34 和 30 交换位置：现在下标 1 是 34、下标 2 是 30。
- 8比较相邻的 30 和 5：拼成 "305" 和 "530"，后者大，说明 5 该排在前，要交换。
- 9因为 "530" 比 "305" 大，把 5 和 30 交换位置：现在下标 2 是 5、下标 3 是 30。
- 10比较相邻的 30 和 9：拼成 "309" 和 "930"，后者大，说明 9 该排在前，要交换。
- 11因为 "930" 比 "309" 大，把 9 和 30 交换位置：现在下标 3 是 9、下标 4 是 30。
- 12这一趟走完，最该排在末尾的数已经沉到右边（标蓝的就是已确定位置的）。下一趟只需处理左边没排好的部分。
- 13比较相邻的 3 和 34：拼成 "334" 和 "343"，后者大，说明 34 该排在前，要交换。
- 14因为 "343" 比 "334" 大，把 34 和 3 交换位置：现在下标 0 是 34、下标 1 是 3。
- 15比较相邻的 3 和 5：拼成 "35" 和 "53"，后者大，说明 5 该排在前，要交换。
- 16因为 "53" 比 "35" 大，把 5 和 3 交换位置：现在下标 1 是 5、下标 2 是 3。
- 17比较相邻的 3 和 9：拼成 "39" 和 "93"，后者大，说明 9 该排在前，要交换。
- 18因为 "93" 比 "39" 大，把 9 和 3 交换位置：现在下标 2 是 9、下标 3 是 3。
- 19这一趟走完，最该排在末尾的数已经沉到右边（标蓝的就是已确定位置的）。下一趟只需处理左边没排好的部分。
- 20比较相邻的 34 和 5：拼成 "345" 和 "534"，后者大，说明 5 该排在前，要交换。
- 21因为 "534" 比 "345" 大，把 5 和 34 交换位置：现在下标 0 是 5、下标 1 是 34。
- 22比较相邻的 34 和 9：拼成 "349" 和 "934"，后者大，说明 9 该排在前，要交换。
- 23因为 "934" 比 "349" 大，把 9 和 34 交换位置：现在下标 1 是 9、下标 2 是 34。
- 24这一趟走完，最该排在末尾的数已经沉到右边（标蓝的就是已确定位置的）。下一趟只需处理左边没排好的部分。
- 25比较相邻的 5 和 9：拼成 "59" 和 "95"，后者大，说明 9 该排在前，要交换。
- 26因为 "95" 比 "59" 大，把 9 和 5 交换位置：现在下标 0 是 9、下标 1 是 5。
- 27这一趟走完，最该排在末尾的数已经沉到右边（标蓝的就是已确定位置的）。下一趟只需处理左边没排好的部分。
- 28所有相邻对都比较过、不再交换，排序结束。整组数已按「拼接更大者在前」排好。
- 29把排好的数从左到右首尾拼起来，就得到最大数 9534330。（若首位是 0，说明全是 0，直接返回 "0"。）
⚠️ 容易写错的地方
✗ 错：按数值大小排序（34 比 9 大就排前面）
✓ 对：按拼接 a+b 与 b+a 比较
9 拼在前是 "934"，34 拼在前是 "349"，9 该在前——数值大小会排反
✗ 错：忘了特判全是 0 的情况
✓ 对：拼完若首位是 '0' 就返回 "0"
nums=[0,0] 会拼成 "00"，必须收敛成 "0"
✗ 错：直接对整数排序而不转字符串
✓ 对：先全部 map 成字符串再比较拼接
比较的是字符串拼接结果，整数无法做 a+b/b+a 这种拼接比较
完整代码（Python / C++ / Java）
Python
from functools import cmp_to_key
def largestNumber(nums):
arr = list(map(str, nums))
# a 排 b 前 ⇔ a+b 比 b+a 大 → 返回 -1
def cmp(a, b):
if a + b > b + a: return -1
if a + b < b + a: return 1
return 0
arr.sort(key=cmp_to_key(cmp))
res = ''.join(arr)
return '0' if res[0] == '0' else res # 防全 0C++
string largestNumber(vector<int>& nums){
vector<string> a;
for (int x : nums) a.push_back(to_string(x));
sort(a.begin(), a.end(), [](auto& x, auto& y){
return x + y > y + x; // x 排前面
});
string res;
for (auto& s : a) res += s;
return res[0] == '0' ? "0" : res;
}Java
public String largestNumber(int[] nums) {
String[] a = new String[nums.length];
for (int i = 0; i < nums.length; i++)
a[i] = String.valueOf(nums[i]);
Arrays.sort(a, (x, y) -> (y + x).compareTo(x + y));
StringBuilder sb = new StringBuilder();
for (String s : a) sb.append(s);
String res = sb.toString();
return res.charAt(0) == '0' ? "0" : res;
}复杂度
时间
O(n log n · k)
排序 O(n log n) 次比较，每次比较是长度约 k 的字符串拼接与比较
空间
O(n · k)
把每个数转成字符串存下来，k 为单个数字的位数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这个比较规则能保证全局最大？+
这个两两比较满足传递性（可证 a+b>b+a 与 b+c>c+b 能推出 a+c>c+a），所以局部最优的两两顺序拼起来就是全局最优，排序得到的整体顺序即最大拼接。
输入里有 0 要注意什么？+
排序后若开头是若干个 0（如 [0,0]），拼接结果会是 "00"。必须特判：首字符是 '0' 就直接返回 "0"。
为什么要先转成字符串？+
比较规则是 a+b 与 b+a 的字符串拼接谁大，整数没法直接拼接比较；转成字符串后用语言内置的字符串比较即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 最大数 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。