跳到主要内容

贪心算法

为什么贪心算法很重要​

贪心算法在每一步做出局部最优选择——通常能得到全局最优解：

  • 区间调度：最大化不重叠任务数量
  • Huffman 编码：最优数据压缩
  • 最短路径：Dijkstra 算法
  • 最小生成树：Prim 和 Kruskal 算法

实际影响：

  • 活动选择：贪心选择最早结束时间 → O(n log n) vs O(2ⁿ) 暴力搜索。
  • Huffman 编码：文本文件压缩率可达 20-50%。
  • 找零钱：对美国硬币面额最优（贪心有效），但对某些特定的硬币系统会失败。

贪心何时有效：

  1. 贪心选择性质：局部最优选择可以导出全局最优解。
  2. 最优子结构：问题的最优解包含其子问题的最优解。

核心概念​

贪心策略​

在每一步，做出当前看起来最好的选择：

经典贪心问题​

问题贪心策略时间复杂度
活动选择最早结束时间O(n log n)
分数背包最高价值/重量比O(n log n)
Huffman 编码合并最小频率O(n log n)
最小生成树最轻的边O(E log V)

贪心 vs 动态规划​

方面贪心动态规划 (DP)
决策方式局部最优探索所有选项
速度更快（通常 O(n log n)）更慢（多项式级别）
最优性不总是保证始终保证
回溯无有

深入理解​

活动选择 (Activity Selection)​

选择数量最多的不重叠活动：

public int activitySelection(int[] start, int[] end) {
    int n = start.length;
    int[][] activities = new int[n][2];

    for (int i = 0; i < n; i++) {
        activities[i] = new int[]{start[i], end[i]};
    }

    // 按结束时间升序排序
    Arrays.sort(activities, (a, b) -> a[1] - b[1]);

    int count = 1;
    int lastEnd = activities[0][1];

    for (int i = 1; i < n; i++) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }

    return count;
}

为什么有效：选择最早结束的时间为剩余活动留出了最大的空间。

分数背包 (Fractional Knapsack)​

class Item {
    int value, weight;

    double getValuePerWeight() {
        return (double) value / weight;
    }
}

public double fractionalKnapsack(Item[] items, int capacity) {
    // 按单位重量价值降序排序
    Arrays.sort(items, (a, b) ->
        Double.compare(b.getValuePerWeight(), a.getValuePerWeight()));

    double totalValue = 0;

    for (Item item : items) {
        if (capacity >= item.weight) {
            // 装入整个物品
            totalValue += item.value;
            capacity -= item.weight;
        } else {
            // 装入物品的一部分
            totalValue += item.getValuePerWeight() * capacity;
            break;
        }
    }

    return totalValue;
}

贪心选择：优先选取单位价值（价值/重量比）最高的物品。

Huffman 编码 (Huffman Coding)​

构建用于压缩的最优前缀编码：

class HuffmanNode implements Comparable<HuffmanNode> {
    char character;
    int frequency;
    HuffmanNode left, right;

    boolean isLeaf() { return left == null && right == null; }

    @Override
    public int compareTo(HuffmanNode other) {
        return this.frequency - other.frequency;
    }
}

public Map<Character, String> huffmanCoding(String text) {
    // 统计频率
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : text.toCharArray()) {
        freq.merge(c, 1, Integer::sum);
    }

    // 构建优先队列
    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
    for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
        HuffmanNode node = new HuffmanNode();
        node.character = entry.getKey();
        node.frequency = entry.getValue();
        pq.offer(node);
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();

        HuffmanNode parent = new HuffmanNode();
        parent.frequency = left.frequency + right.frequency;
        parent.left = left;
        parent.right = right;
        pq.offer(parent);
    }

    // 生成编码表
    Map<Character, String> codes = new HashMap<>();
    buildCodes(pq.peek(), "", codes);
    return codes;
}

private void buildCodes(HuffmanNode node, String code,
                       Map<Character, String> codes) {
    if (node.isLeaf()) {
        codes.put(node.character, code.isEmpty() ? "0" : code);
        return;
    }
    buildCodes(node.left, code + "0", codes);
    buildCodes(node.right, code + "1", codes);
}

实际应用​

最小找零枚数​

public int minCoins(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;

    for (int i = coins.length - 1; i >= 0; i--) {
        if (coins[i] <= amount) {
            int num = amount / coins[i];
            count += num;
            amount -= num * coins[i];
        }
        if (amount == 0) break;
    }

    return amount == 0 ? count : -1;
}

注意：贪心并不适用于所有硬币系统（如 coins = [1, 3, 4], amount = 6 时，贪心解为 4+1+1 共三枚，而最优解为 3+3 共两枚）。

跳跃游戏 (Jump Game)​

public boolean canJump(int[] nums) {
    int maxReach = 0;

    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    return true;
}

面试题​

Q1：分发饼干 (简单)​

题目：用有限的饼干最大化满足孩子的数量。

方法：贪心匹配——用能满足孩子胃口的最小饼干。

复杂度：O(n log n + m log m) 时间。

public int findContentChildren(int[] greed, int[] size) {
    Arrays.sort(greed);
    Arrays.sort(size);

    int child = 0, cookie = 0;

    while (child < greed.length && cookie < size.length) {
        if (size[cookie] >= greed[child]) {
            child++;
        }
        cookie++;
    }

    return child;
}

Q2：加油站 (中等)​

题目：找到能完成环路的起始加油站。

方法：贪心思路，配合总油量检查。

复杂度：O(n) 时间。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0, totalCost = 0;
    int currentGas = 0, start = 0;

    for (int i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];

        currentGas += gas[i] - cost[i];

        if (currentGas < 0) {
            start = i + 1;
            currentGas = 0;
        }
    }

    return totalGas >= totalCost ? start : -1;
}

延伸阅读​

  • 动态规划：用于解决贪心算法失效的优化问题。
  • 堆 (Heaps)：常用于贪心算法中（如 Huffman 树构建）。
  • 贪心应用：区间调度、最小生成树 (MST)。
  • LeetCode：贪心标签题目