贪心算法 -- 组合一组数字获得最大数

贪心算法 – 组合一组数字获得最大数

题目重现

题目链接：最大数 - 力扣

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出：“210”

示例 2：

输入：nums = [3,30,34,5,9]
输出：“9534330”

读懂题目

这道题目有三个注意点：

• 组合得到的结果可能很大，返回值类型是字符串（string）
• 如果组合得到的字符串以 ‘0’ 开头，那么后续字符也只可能是 ‘0’，因为题目的核心条件是组合得到的数字尽可能大，这里返回结果需要截断后面所有字符 ‘0’，仅返回 “0” 即可。
• 最终得到的字符串需要有一定的规则决定哪个数字优先做高位被插入字符串中，所以这组数某种意义上是有序的，将这组数字按照指定顺序存入容器中，就可以逐个按顺序取出直接插入字符串，得到的结果是理想的最大数。

处理细节：

由于每次仅需取到当前容器剩余数中最符合要求的一个数字，所以符合堆的特性，我们可以选用优先队列 priority_queue 来存储这组数。

对于上面注意点中提到的以某种特定规则对这组数进行排序，这种排序规则的指定可以通过传递谓词实现，为了方便实现，我们可以定义 lambda 表达式并将其表达式自身类型和表达式对象分别传入 priority_queue 的构造模板列表和构造函数参数列表。

另外注意 priority_queue 实例化对象时的参数列表：

为了便于对这组数设定排序谓词，不妨将其全部转为字符串类型再 push 进优先队列，同时我们将要作为谓词的 lambda 表达式的参数设定为 string 类型即可。

贪心场景

整个题选用优先队列存储各个数据，最后将其逐个 pop() 得到的对象追加在结果字符串中，这即是贪心策略的最明显体现。

代码示例

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        auto comp = [&](const string& s1, const string& s2)
        {
            return s1 + s2 < s2 + s1;
        };

        priority_queue<std::string, vector<string>, decltype(comp)> pq(comp);
        for (auto e : nums) {
            pq.push(to_string(e));
        }

        std::string result;
        for (; !pq.empty();) {
            result += pq.top();
            pq.pop();
        }

        if(result[0] == '0') { return "0"; }
        return result;
    }
};

提交结果：