每日一题-力扣-179-最大数

JAY.LIN 收录于每日一题

2025-03-13 约 1005 字预计阅读 3 分钟

https://bing.ee123.net/img/rand?artid=146244983

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

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

📋 问题描述

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

💡 核心思路

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

关键步骤 ：

🔍 全零检测 ：若输入全为 0 ，直接返回 "0" 。
🔄 字符串转换 ：将每个数字转为字符串，避免大数拼接时的溢出问题。
📊 自定义排序 ：按 a+b > b+a 的字典序降序排列。
🧩 拼接结果 ：直接拼接排序后的字符串。
⚠️ 处理前导零 ：仅在结果全零时返回 "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" ✅。
优化点 ：无需反转字符串，直接遍历一次即可🚀。

📊 示例验证

输入	输出	说明
`[10, 2]`	`"210"` ✅	正确排序 `"10"` 和 `"2"`
`[3, 30, 34, 5, 9]`	`"9534330"` ✅	正确处理多位数拼接顺序
`[0, 0, 0]`	`"0"` ✅	全零检测正确触发
`[0, 1, 0]`	`"100"` ✅	前导零处理正确

⏱️ 复杂度分析

步骤	时间复杂度	空间复杂度
全零检测	O(n)	O(1)
字符串转换	O(n)	O(n)
自定义排序	O(n log n)	O(log n)
拼接结果	O(nk)	O(nk)
处理前导零	O(n)	O(1)
总计	O(nk log n)	O(nk)

Yes

Start

All zeros?

Return 0

Convert to strings

Sort by a+b > b+a

Concatenate

Leading zeros?

Trim leading zeros

Keep result

Output

🚀 优化总结

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