(每日一题) 力扣 179 最大数

🎯 LeetCode 179 最大数：最优解法详解（C++实现）

📋 问题描述

给定一组非负整数 nums，重新排列每个数的顺序，使其组成一个最大的整数。例如，输入 [3, 30, 34, 5, 9]，输出应为 "9534330"。由于结果可能非常大，需返回字符串而非整数。

💡 核心思路

贪心策略：通过自定义排序规则，确保每两个数字的拼接结果局部最优，从而得到全局最大值。
关键步骤：

1. 🔍 全零检测：若输入全为 0，直接返回 "0"。
2. 🔄 字符串转换：将每个数字转为字符串，避免大数拼接时的溢出问题。
3. 📊 自定义排序：按 a+b > b+a 的字典序降序排列。
4. 🧩 拼接结果：直接拼接排序后的字符串。
5. ⚠️ 处理前导零：仅在结果全零时返回 "0"。

🚀 完整代码实现

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

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        // 1. 🔍 全零检测
        if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) {
            return "0";
        }
        
        // 2. 🔄 转换为字符串数组
        vector<string> strs;
        for (int num : nums) {
            strs.push_back(to_string(num));
        }
        
        // 3. 📊 自定义排序：a+b > b+a
        sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });
        
        // 4. 🧩 拼接结果
        string result;
        for (const string& s : strs) {
            result += s;
        }
        
        // 5. ⚠️ 处理前导零
        size_t start = 0;
        while (start < result.size() && result[start] == '0') start++;
        return (start == result.size()) ? "0" : result.substr(start);
    }
};

🔍 分步解析

1. 全零检测

if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) {
    return "0";
}

• 作用：若输入全为 0（例如 [0, 0, 0]），直接返回 "0"✅，避免后续无效操作。
• 复杂度：⏱️ 时间复杂度 O(n)，🗃️ 空间复杂度 O(1)。

2. 字符串转换

vector<string> strs;
for (int num : nums) {
    strs.push_back(to_string(num));
}

• 优化点：提前转换所有数字为字符串，避免排序时重复调用 to_string🚀。
• 复杂度：⏱️ O(n)，🗃️ O(n)。

3. 自定义排序规则

sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    return a + b > b + a;
});

• 核心逻辑：比较两种拼接方式 a+b 和 b+a 的字典序。
  • 示例：比较 "3" 和 "30"，"330" > "303"，因此 "3" 排在 "30" 前👉。
• 复杂度：⏱️ 排序 O(n log n)，字符串比较 O(k)（k 为字符串平均长度）。

4. 拼接结果

string result;
for (const string& s : strs) {
    result += s;
}

• 复杂度：⏱️ O(nk)，🗃️ O(nk)（k 为字符串平均长度）。

5. 处理前导零

size_t start = 0;
while (start < result.size() && result[start] == '0') start++;
return (start == result.size()) ? "0" : result.substr(start);

• 作用：跳过前导零，若结果全零则返回 "0"✅。
• 优化点：无需反转字符串，直接遍历一次即可🚀。

📊 示例验证

⏱️ 复杂度分析

🚀 优化总结

1. 避免冗余操作：直接遍历处理前导零，而非反转字符串✅。
2. 减少重复转换：提前将数字转为字符串数组，节省排序时间🚀。
3. 贪心策略正确性：通过字典序比较保证局部最优解即为全局最优💡。