贪心算法实战：从柠檬水找零到数组减半与最大数拼接

二、2208. 将数组和减半的最少操作次数

1. 题目解析

题意很直观，每次操作将一个数字减半，目标是让总和减少一半所需的操作次数最少。

2. 算法原理

为了让总和下降最快，每次都应该选择当前数组中的最大值进行减半。这提示我们需要一个能快速获取最大值的数据结构——大根堆。

具体步骤如下：

1. 将所有元素放入大根堆中。
2. 计算初始总和，目标是将总和减去一半。
3. 循环取出堆顶最大值，将其减半后放回堆中，同时更新剩余需要减去的数值。
4. 统计操作次数。

3. 代码实现

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0;
        for (int x : nums) {
            sum += x;
            q.offer((double) x);
        }
        int ret = 0;
        sum /= 2.0;
        while (sum > 0) {
            double t = q.poll() / 2.0;
            sum -= t;
            q.offer(t);
            ret++;
        }
        return ret;
    }
}

三、179. 最大数

1. 题目解析

给定一组非负整数，将它们排列成一个大整数并返回字符串形式。关键在于如何定义两个数字的'大小'关系。

2. 算法原理

我们可以通过类比常见的排序算法来解决。核心是确立自定义的排序规则：

1. 假设数组中有 a 和 b 两个数字，比较 ab 和 ba 的大小（拼接后的字符串）。
2. 如果 ab > ba，则 a 排在 b 前面；反之 b 排在 a 前面。
3. 按照这个规则对整个数组排序即可得到最大数。

注意点：

• 如果排序后第一个字符是 '0'，说明所有数字都是 0，直接返回 "0"。
• 比较时需先将数字转为字符串，再进行字典序拼接比较。

3. 代码实现

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = "" + nums[i];
        }
        Arrays.sort(s, (a, b) -> (b + a).compareTo(a + b));
        StringBuilder ret = new StringBuilder();
        for (String str : s) {
            ret.append(str);
        }
        if (ret.charAt(0) == '0') {
            return "0";
        }
        return ret.toString();
    }
}