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

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

1. 题目解析

题意即通过最少的操作次数，使数组元素之和减少到原来的一半。每次操作可以将任意一个元素除以 2。

2. 算法原理

核心策略非常直观：为了让总和下降最快，每次都应该选择当前最大的元素进行减半。

为了实现这一点，我们需要一个大根堆（优先队列），将所有元素放入其中。每次取出堆顶最大值，减半后再放回堆中，直到总和满足条件。

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. 算法原理

这道题的关键在于确定排序规则。我们不能简单地按数值大小排序，而是要比较拼接后的结果。

假设数组中有两个数字 a 和 b，如果 ab（拼接）大于 ba，则 a 应该排在 b 前面；反之则 b 在前。基于这个自定义规则对数组排序后，依次拼接即可得到最大数。

另外要注意一个边界情况：如果排序后第一个字符是 '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();
    }
}