贪心算法实战：三道经典 LeetCode 题解

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

思路分析

题目要求通过最少的操作次数（每次将一个数减半），使数组总和减少一半以上。

要让总和下降最快，直觉上我们应该每次都减小当前数组中最大的那个数。这提示我们使用**大根堆（PriorityQueue）**来维护元素。

需要注意的是，由于涉及浮点数运算且精度可能影响比较结果，建议将整数转换为 Double 类型存入堆中。同时，计算目标值时也要用浮点数处理。

参考实现

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

三、最大数 (179)

思路分析

给定一组非负整数，将它们拼接成一个最大的整数。这看起来像是一个排序问题，但标准的数值大小排序并不适用。

我们需要自定义排序规则：对于两个数字字符串 a 和 b，如果 a + b 大于 b + a，则 a 应该排在 b 前面。通过这种字典序的比较逻辑，我们可以确定最终的拼接顺序。

边界情况：如果排序后第一个字符是 '0'，说明所有输入都是 0，此时应直接返回 "0"，避免输出类似 "00...0" 的结果。

参考实现

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
        
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        
        // 处理全为 0 的情况
        if (sb.charAt(0) == '0') {
            return "0";
        }
        
        return sb.toString();
    }
}

总结

这三道题分别展示了贪心算法在状态模拟、数据结构优化以及自定义排序三个维度的应用。在实际解题中，识别出'局部最优'与'全局最优'的关系是关键。希望这些案例能帮助你更好地掌握贪心策略。