贪心算法实战：破解技术面试中的5大经典问题

在技术面试中，算法能力往往是区分候选人的关键因素。而贪心算法作为一种高效且直观的解题思路，几乎成为每位面试官必考的内容。本文将深入剖析贪心算法的核心思想，并通过5个经典问题的Java实现，帮助你在面试中游刃有余。

1. 贪心算法核心思想解析

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优决策的算法策略。它不像动态规划那样考虑全局最优，而是通过局部最优的累积来逼近整体最优解。这种特性使得贪心算法在解决某些特定类型问题时表现出极高的效率。

贪心算法的两大关键性质：

1. 贪心选择性质 ：问题的整体最优解可以通过一系列局部最优选择达到。这意味着我们不需要考虑子问题的解，只需做出当前最佳选择。
2. 最优子结构 ：问题的最优解包含其子问题的最优解。这一性质保证了局部最优解能够组合成全局最优解。

值得注意的是，并非所有问题都适合使用贪心算法。在使用前必须验证问题是否具备上述两个性质，否则可能得到次优解。

贪心算法的典型应用场景包括：

• 活动安排问题
• 货币找零问题
• 最小生成树（Prim和Kruskal算法）
• 霍夫曼编码
• 任务调度问题

2. 活动选择问题：最大化活动安排

活动选择问题是贪心算法的经典应用场景。假设有一组活动，每个活动有开始时间和结束时间，如何安排才能使尽可能多的活动不发生时间冲突？

贪心策略 ：总是选择结束时间最早的活动，这样可以为后续活动留下更多时间。

public class ActivitySelection {
    public static List<Integer> selectActivities(int[] start, int[] end) {
        List<Integer> result = new ArrayList<>();
        // 假设活动已按结束时间排序
        result.add(0); // 选择第一个活动
        int lastEnd = end[0];
        
        for (int i = 1; i < end.length; i++) {
            if (start[i] >= lastEnd) {
                result.add(i);
                lastEnd = end[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] end = {2, 4, 6, 7, 9, 9};
        List<Integer> selected = selectActivities(start, end);
        System.out.println("Selected activities: " + selected);
    }
}

时间复杂度分析 ：O(nlogn)（主要来自排序），空间复杂度O(1)

提示：活动选择问题也可以使用动态规划解决，但贪心算法通常更高效。

3. 货币找零问题：最小化纸币数量

给定不同面额的货币和一个总金额，如何用最少数量的货币凑成这个金额？这是日常生活中常见的贪心算法应用。

贪心策略 ：每次尽可能使用最大面额的货币。

public class CoinChange {
    public static int[] minCoins(int[] coins, int amount) {
        int[] result = new int[coins.length];
        // 假设coins已按降序排列
        for (int i = 0; i < coins.length; i++) {
            result[i] = amount / coins[i];
            amount %= coins[i];
        }
        return amount == 0 ? result : null;
    }

    public static void main(String[] args) {
        int[] coins = {25, 10, 5, 1}; // 美分硬币
        int amount = 63;
        int[] change = minCoins(coins, amount);
        System.out.println("Coin distribution: " + Arrays.toString(change));
    }
}

特殊情况处理 ：当货币面额不满足特定条件时，贪心算法可能无法得到最优解。例如，面额为{1, 3, 4}，要凑6元时，贪心会选择4+1+1，而最优解是3+3。

4. 分数背包问题：最大化价值

在背包问题中，如果物品可以分割（分数背包问题），贪心算法可以得到最优解。

贪心策略 ：按单位重量价值从高到低选择物品。

public class FractionalKnapsack {
    static class Item {
        int weight, value;
        double ratio;
        Item(int w, int v) {
            weight = w;
            value = v;
            ratio = (double)v / w;
        }
    }

    public static double maxValue(Item[] items, int capacity) {
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));
        double totalValue = 0;
        
        for (Item item : items) {
            if (capacity >= item.weight) {
                totalValue += item.value;
                capacity -= item.weight;
            } else {
                totalValue += capacity * item.ratio;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        int capacity = 50;
        System.out.println("Max value: " + maxValue(items, capacity));
    }
}

对比0-1背包 ：分数背包可以使用贪心算法，而0-1背包则需要动态规划解决。

5. 区间调度问题：最小覆盖

给定一组区间，如何选择最少数量的区间来完全覆盖目标区间？

贪心策略 ：每次选择覆盖当前起点且结束最远的区间。

public class IntervalCovering {
    public static int minIntervals(int[][] intervals, int target) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int count = 0, currentEnd = 0, i = 0;
        int n = intervals.length;
        
        while (currentEnd < target && i < n) {
            int maxEnd = currentEnd;
            while (i < n && intervals[i][0] <= currentEnd) {
                maxEnd = Math.max(maxEnd, intervals[i][1]);
                i++;
            }
            if (maxEnd == currentEnd) break;
            currentEnd = maxEnd;
            count++;
        }
        return currentEnd >= target ? count : -1;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4}, {2,5}, {3,6}, {5,7}, {6,8}};
        int target = 8;
        System.out.println("Minimum intervals needed: " + minIntervals(intervals, target));
    }
}

6. 贪心算法的局限性与面试技巧

尽管贪心算法简洁高效，但它并非万能。在面试中，你需要清楚地向面试官说明：

1. 为什么选择贪心算法 ：解释问题满足贪心选择性质和最优子结构
2. 贪心策略的合理性 ：证明你的局部最优选择能导致全局最优
3. 边界条件处理 ：考虑空输入、极端值等情况
4. 替代方案 ：讨论动态规划等其他解法的优缺点

常见面试问题扩展 ：

• 如何证明贪心算法的正确性？
• 贪心算法和动态规划的主要区别是什么？
• 举一个贪心算法失效的例子？

在实际编码面试中，我通常会先写一个暴力解法，然后分析是否可以应用贪心策略优化。这种思路展示了你对问题理解的深度和系统性思考能力。