贪心算法讲解与例题

目录

• 什么是贪心算法
• 贪心的核心思路
• 贪心 vs 动态规划
• 常见贪心题型
• 例题精选

---

什么是贪心算法

贪心算法（Greedy Algorithm）的核心思想是：每一步都做当前看起来最好的选择，并期望这些局部最优最终导致全局最优。

关键特征：

• 不回溯：做了选择就不再反悔
• 只看眼前：不关心未来的影响
• 正确性需要证明：不是所有问题都能用贪心

---

贪心的核心思路

问题：给你一些选择，求最优解

贪心做法：
1. 找出一个「局部最优」的决策规则
2. 按规则排序或逐个处理
3. 每次选当前最优的
4. 最终累加得到全局解

典型模式：

1. 排序 + 贪心：先排好序，再扫一遍做选择
2. 优先队列贪心：用堆维护当前最优选项
3. 区间贪心：按起点/终点排序，做不重叠选择

---

贪心 vs 动态规划

维度	贪心	动态规划
决策方式	每步选最优，不回退	考虑所有可能，记录状态
时间复杂度	通常 O(n log n)	通常 O(n²) 或更高
正确性	需要证明	一定正确（状态完备）
代码量	少	多

判断能否用贪心：

• 如果问题有「贪心选择性质」→ 局部最优能推出全局最优 → 贪心
• 如果问题有「后效性」（当前选择影响后续选项）→ 通常需要 DP
• 如果不确定，先想 DP，再看能否优化成贪心

---

常见贪心题型

1. 区间问题

• 选择最多不重叠区间 → 按结束时间排序
• 合并重叠区间 → 按开始时间排序
• 统计孤立区间 → 排序后检查相邻

2. 分配问题

• 数组分两组使差值最小 → 排序后枚举分割点
• 发饼干/分糖果 → 排序后双指针

3. 序列问题

• 买卖股票（一次交易）→ 记录最低价
• 跳跃游戏 → 维护最远可达位置

4. 哈夫曼编码

• 合并代价最小 → 优先队列取两个最小

---

例题精选

例题 1：最小化两组极差之和

题目：将 n 个整数分成两组（都不能为空），最小化 (max1-min1) + (max2-min2)。

贪心思路：

1. 排序数组
2. 枚举分割点 i：左边 [0, i-1]，右边 [i, n-1]
3. 左边极差 = nums[i-1] - nums[0]
4. 右边极差 = nums[n-1] - nums[i]
5. 取所有分割点的最小值

为什么贪心对：排序后，一组内的 max 和 min 一定在两端，枚举分割点覆盖了所有可能。

function getResult(n, nums) {
    if (n <= 2) return 0;
    nums.sort((a, b) => a - b);
    let min = Infinity;
    for (let i = 1; i < n; i++) {
        const leftRes = nums[i - 1] - nums[0];
        const rightRes = nums[n - 1] - nums[i];
        min = Math.min(min, leftRes + rightRes);
    }
    return min;
}

---

例题 2：统计不重叠区间数量

题目：给定若干区间 [start, end]，统计跟其他任何区间都不重叠的区间数量。

贪心思路：

1. 按起点排序
2. 对每个区间，检查它是否与左右相邻区间重叠
3. 因为排序后，最近的邻居都不重叠 → 更远的邻居也不会重叠

function getCount(list) {
    list.sort((a, b) => a[0] - b[0]);
    let c = 0;
    for (let i = 0; i < list.length; i++) {
        let overlap = false;
        // 检查右边邻居
        if (i + 1 < list.length && list[i][1] >= list[i + 1][0]) {
            overlap = true;
        }
        // 检查左边邻居
        if (i - 1 >= 0 && list[i - 1][1] >= list[i][0]) {
            overlap = true;
        }
        if (!overlap) c++;
    }
    return c;
}

---

例题 3：人偶符法（树 + 贪心）

题目：树上有 n 个节点，每个节点有初始状态和目标状态（0/1）。每次选一个节点，将其子树中与它深度同奇偶的节点全部翻转。求最少操作次数。

贪心思路：从根往下 DFS，每个节点检查：

1. 祖先操作对它的累积影响（evenOp / oddOp）
2. 如果影响 != 需求，就在当前节点操作一次

为什么贪心对：祖先操作影响后代，但后代操作不影响祖先。所以从根往下，每个节点做决定时已经知道所有影响因素，不需要回退。

function dfs(u, p, depth, evenOp, oddOp) {
    const need = (init[u] !== goal[u]) ? 1 : 0;
    const flip = (depth % 2 === 0) ? evenOp : oddOp;

    let curEvenOp = evenOp;
    let curOddOp = oddOp;

    if (flip !== need) {
        ans++;
        if (depth % 2 === 0) {
            curEvenOp = 1 - curEvenOp;
        } else {
            curOddOp = 1 - curOddOp;
        }
    }

    for (const v of tree[u]) {
        if (v === p) continue;
        dfs(v, u, depth + 1, curEvenOp, curOddOp);
    }
}

---

例题 4：经典区间调度（最多不重叠区间）

题目：给定 n 个区间，选出最多数量的互不重叠的区间。

贪心思路：按结束时间排序，每次选结束最早的且不与上一个选的区间重叠的。

function maxNonOverlap(intervals) {
    // 按结束时间排序
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 0;
    let lastEnd = -Infinity;
    for (const [start, end] of intervals) {
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    return count;
}

---

例题 5：跳跃游戏

题目：数组每个位置表示能跳的最远距离，判断能否到达终点。

贪心思路：维护当前能到达的最远位置，如果最远位置覆盖了终点就成功。

function canJump(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false; // 当前位置不可达
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    return false;
}

---

例题 6：买卖股票最佳时机

题目：数组表示每天股价，只能买卖一次，求最大利润。

贪心思路：遍历过程中记录历史最低价，每天算「当天卖出 - 历史最低价」。

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    for (const price of prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

---

总结

技巧	适用场景
排序后扫描	区间问题、分配问题
维护最小值/最大值	股票问题、极差问题
按结束时间贪心	最多不重叠区间
自上而下传递状态	树形贪心（无后效性）
优先队列	哈夫曼编码、合并问题

核心口诀：排序排好，贪心选好，证明对了就对了。不确定时先想 DP，再看能不能贪心。