0179. Largest Number

题目信息

题号:
  1. 最大数

难度:

Medium

主题:

字符串、排序、自定义比较器、交换论证

原题:

LeetCode 0179

重点:

将全排列压缩为两元素拼接顺序,用 a+b 与 b+a 决定局部次序并证明全局最优

题目重述

给定非负整数数组 nums,重新排列所有元素,将它们的十进制文本依次拼接,使结果尽可能 大。每个元素必须恰好使用一次,返回结果字符串。

完整结果可能超过固定宽度整数,所以不能以数值类型返回。若输入全为 0,规范结果是单个 "0",不是带多个前导零的字符串。

自建示例

输入:nums = [3,30,34,5,9]
输出:"9534330"

排列顺序为 9、5、34、3、30;数值 30 虽大于 3,却必须放在 3 后面。
输入:nums = [121,12]
输出:"12121"

"12" + "121" 大于 "121" + "12",所以 12 应在 121 前面。
输入:nums = [0,0,0]
输出:"0"

C++ 实现

#include <algorithm>
#include <string>
#include <vector>

class Solution {
public:
    std::string largestNumber(std::vector<int>& nums) {
        std::vector<std::string> parts;
        parts.reserve(nums.size());
        for (int value : nums) {
            parts.push_back(std::to_string(value));
        }

        std::sort(
            parts.begin(),
            parts.end(),
            [](const std::string& left, const std::string& right) {
                return left + right > right + left;
            });

        if (parts.front() == "0") {
            return "0";
        }

        std::size_t total_length = 0;
        for (const std::string& part : parts) {
            total_length += part.size();
        }

        std::string answer;
        answer.reserve(total_length);
        for (const std::string& part : parts) {
            answer += part;
        }
        return answer;
    }
};

题解

原始搜索空间是全部排列

按照题意,可以生成 n! 个元素排列,逐个拼接并取最大字符串。它不会遗漏答案,但每次 排列只改变少数相对顺序,大量前后片段被重复构造和比较。瓶颈是没有回答更基本的问题: 任取两个元素 a、b,它们谁在前面更有利?

普通数值降序不能回答。对 3 与 30,数值上 30 更大,但 330 > 303,所以 3 必须在 前。普通字符串字典序也不足:"121" 因为是 "12" 的更长前缀会被排在前面, 但 12112 < 12121,正确顺序恰好相反。

两元素的完整比较

固定排列中其余元素,只比较相邻的 a、b。两种候选结果拥有相同的外部前缀和 后缀,差异只在中间块:

... + a + b + ...
... + b + a + ...

因此若 a + b > b + a,就让 a 排在 b 前面。两个拼接串长度相同且都只含 十进制数字,字符串字典序与它们代表的大整数顺序一致;无需把可能溢出的拼接结果转换成 整数。

示例中:

3 与 30:  "330" > "303",所以 3 在前
12 与 121:"12121" > "12112",所以 12 在前

这个规则比较的是完整交叉拼接,不是首字符、更长文本或数值大小等局部特征。

比较器为何可以交给排序

可以把每个非空字符串无限重复,例如 "12" 变成 121212...。比较 a + b 与 b + a 的结果,等价于比较 a、b 两个无限周期串的字典序: 第一处不同字符会在一个共同周期内出现;若永远没有差异,则 a+b == b+a。

无限字符串字典序具有传递性和不对称性,相同周期串形成等价类,所以 a+b > b+a 是 std::sort 可以使用的严格弱序。等价元素无论谁在前,局部拼接都 相同,不需要稳定排序。

局部顺序为何得到全局最大

假设某个排列含相邻逆序 b,a,而比较器认为 a+b > b+a。交换这两个元素时, 排列的公共前缀和后缀完全不变,中间块从 b+a 变为更大的 a+b,所以完整结果严格 增大。

不断交换逆序相邻对,有限步后得到比较器排序结果,过程中拼接值只增不减。任意初始排列 都能这样转成排序结果,因此排序结果不小于任何排列,也就是全局最大值。排序一次就取代了 对全部排列的重复构造。

代码状态走读

parts 先保存所有十进制文本,避免排序比较时反复调用 to_string。排序后的数组已 满足每个相邻对都采用更优拼接顺序,最终只需从左到右追加。

answer.reserve(total_length) 先计算结果总长度并预留空间,减少字符串增长时的重复 扩容;它不参与正确性,只删除构造阶段的内存搬移。

排序后若首项是 "0",就不可能还有正数:任何正数字符串与 "0" 比较时都会 排在它前面。因此所有元素必为 0,直接返回 "0",避免产生 "000"。不能无条件 删除前导零,因为每个原始非零数的文本本来就没有前导零,只有全零输入需要归一化。

复杂度

设元素数为 n,单个数字文本最大长度为 k,全部文本总长度为 D。转换与最终 拼接需要 O(D) 时间;排序进行 O(n log n) 次比较,每次构造并比较长度至多 2k 的拼接串,时间上界为 O(n k log n)。字符串数组和答案占 O(D) 空间, 比较器产生的临时拼接串占 O(k) 峰值空间。