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

每次操作可以将一个数减半，求使总和减少一半所需的最少操作次数。 直觉上，每次削减最大的数，对总和的影响最大。

解题思路

使用大根堆（优先队列）存储所有元素。 循环取出堆顶最大值，将其减半后放回堆中，同时累加已减去的量。 当累计减去量达到总和的一半时停止。

代码实现

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq = new PriorityQueue<>((a, b) -> Double.compare(b, a));
        double sum = 0;
        for (int num : nums) {
            double val = (double) num;
            sum += val;
            pq.offer(val);
        }
        
        double target = sum / 2.0;
        double reduced = 0;
        int ops = 0;
        
        while (reduced < target) {
            double top = pq.poll();
            double half = top / 2.0;
            reduced += (top - half);
            pq.offer(half);
            ops++;
        }
        return ops;
    }
}

三、最大数

题目分析

给定一组非负整数，将它们排列成一个大整数返回。 核心在于确定两个数字拼接的顺序。

解题思路

自定义排序规则：对于字符串 a 和 b，如果 b + a 大于 a + b，则 b 排在 a 前面。 排序完成后拼接即可。 注意全为 0 的情况，结果应为 "0" 而不是 "00..."。

代码实现

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