贪心算法 (Greedy Algorithm)

1. 贪心算法核心概览

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

通俗理解： “活在当下，绝不后悔”。只顾眼前的最大利益，每次都选看起来最爽的，选完之后绝对不回溯去修改之前的决定。

1.1 贪心算法的两大核心性质

一个问题想要用贪心算法解决，并且得到正确的全局最优解，通常需要满足以下两个性质：

核心性质	详细说明
1. 贪心选择性质	我们可以通过做出局部最优的选择，来构建全局最优解。也就是说，我们不需要考虑未来的情况，眼前的最优就是整体最优的基础。
2. 最优子结构	问题的最优解包含其子问题的最优解。（这一点和动态规划一样，但贪心更极端，它直接舍弃了其他所有非贪心的可能性）。

1.2 贪心算法与动态规划 (DP) 的恩怨情仇

这是面试中最常被问到的问题。一句话总结：贪心是目光短浅的 DP。

• 动态规划： 纵观全局，推演所有可能的状态，保留每个子问题的解，最终得出最优解。（有记忆，可反悔，绝对能找到最优解）。
• 贪心算法： 一条路走到黑，只看眼前最优，不记录其他状态，不反悔。（速度极快，空间占用极小，但不一定能得到全局最优解）。

2. 经典贪心场景与 JavaScript 实现

2.1 找零问题 (贪心版) - 深刻理解贪心的局限性

适用情况： 如果硬币面值是 [25, 10, 5, 1]（现实中的货币系统），贪心算法绝对成立。因为最大面值总是前面面值的倍数，尽量用大面值肯定是最优的。

失效情况： 如果硬币面值是 [4, 3, 1]，凑 6 元。贪心会选 4 + 1 + 1（3枚），但实际最优解是 3 + 3（2枚）。此时贪心失效，必须用 DP！

JavaScript 代码实现 (针对标准货币体系的贪心解法)

/**
 * 找零钱 - 贪心算法 (假设硬币系统合理)
 * 每次优先使用面值最大的硬币
 * @param {number[]} coins 硬币面值数组
 * @param {number} amount 目标金额
 * @return {number} 最少硬币数
 */
function coinChangeGreedy(coins, amount) {
    // 1. 将硬币按面值从大到小排序
    coins.sort((a, b) => b - a);
    
    let count = 0;
    
    for (let i = 0; i < coins.length; i++) {
        const coin = coins[i];
        if (amount === 0) break; // 已经凑齐
        
        // 2. 只要当前金额大于面值，就尽可能多地使用这种大面额硬币
        if (amount >= coin) {
            count += Math.floor(amount / coin); // 计算能用几枚当前硬币
            amount = amount % coin; // 剩下还需要凑的金额
        }
    }
    
    return amount === 0 ? count : -1; 
}

console.log(coinChangeGreedy([25, 10, 5, 1], 67)); 
// 输出: 4 (计算过程: 2个25, 1个10, 0个5, 2个1 -> 25*2 + 10 + 1*2)

2.2 分发饼干 (Assign Cookies) - 经典双指针贪心

题目描述： 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。每个孩子 i 都有一个胃口值 g[i]，每块饼干 j 都有一个尺寸 s[j]。如果 s[j] >= g[i]，就可以满足这个孩子。求最多能满足多少个孩子。

贪心策略：

1. 优先满足胃口最小的孩子（因为他们最容易被满足）。
2. 用能满足该孩子的、尺寸最小的饼干（把大饼干省下来给胃口大的孩子）。

JavaScript 代码实现

/**
 * 分发饼干
 * @param {number[]} g 孩子们胃口数组
 * @param {number[]} s 饼干尺寸数组
 * @return {number} 最多满足的孩子数
 */
function findContentChildren(g, s) {
    // 1. 数组都要从小到大排序
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);

    let child = 0;  // 孩子指针
    let cookie = 0; // 饼干指针

    // 2. 遍历饼干和孩子
    while (child < g.length && cookie < s.length) {
        // 如果当前饼干能满足当前孩子
        if (s[cookie] >= g[child]) {
            child++; // 孩子被满足，指针后移，去看下一个胃口更大的孩子
        }
        // 无论是否满足，当前饼干都被消耗（或因为太小被丢弃），去看下一块更大的饼干
        cookie++;
    }

    return child; // child 的值正好就是被满足的孩子数量
}

2.3 跳跃游戏 (Jump Game) - 覆盖范围贪心

题目描述： 给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。 例如：nums = [2,3,1,1,4] 返回 true。nums = [3,2,1,0,4] 返回 false。

贪心策略： 没必要去纠结到底每一步跳多远，我们只关注当前能覆盖到的最远距离（Max Reach）。只要遍历过程中，有一个最远距离能盖住终点，就成功了。

JavaScript 代码实现

/**
 * 跳跃游戏
 * @param {number[]} nums
 * @return {boolean}
 */
function canJump(nums) {
    let maxReach = 0; // 当前能跳到的最远下标

    for (let i = 0; i < nums.length; i++) {
        // 如果当前下标已经超过了我们能到达的最远距离，说明卡死在前面了，永远走不到这
        if (i > maxReach) {
            return false;
        }
        
        // 更新最远覆盖距离：当前位置 i 加上当前位置能跳的步数 nums[i]
        maxReach = Math.max(maxReach, i + nums[i]);
        
        // 如果最远距离已经能盖住最后一个下标，提前宣布胜利
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }
    
    return true;
}

2.4 无重叠区间 / 区间调度 - 极高频面试题

题目描述： 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 例如：[[1,2], [2,3], [3,4], [1,3]]。移除 [1,3] 后，剩下的互不重叠，返回 1。

贪心策略： 如果想保留最多的区间，那么每次我们都应该选择结束时间最早的区间！因为它留给后面区间的空间最大。

JavaScript 代码实现

/**
 * 无重叠区间
 * @param {number[][]} intervals
 * @return {number}
 */
function eraseOverlapIntervals(intervals) {
    if (intervals.length === 0) return 0;

    // 1. 按照区间的结束时间（右边界）从小到大排序
    intervals.sort((a, b) => a[1] - b[1]);

    let count = 1; // 记录非重叠区间的数量（至少有1个，即排序后的第一个）
    let currentEnd = intervals[0][1]; // 记录当前互不重叠区间的最后结束时间

    // 2. 从第二个区间开始遍历
    for (let i = 1; i < intervals.length; i++) {
        // 如果当前区间的开始时间 >= 我们记录的最后结束时间，说明不重叠
        if (intervals[i][0] >= currentEnd) {
            count++; // 不重叠区间数量 +1
            currentEnd = intervals[i][1]; // 更新最后结束时间
        }
    }

    // 题目要求的是“移除的数量”，所以用总长度减去不重叠的数量
    return intervals.length - count;
}

3. 常见问题深度剖析 (FAQ)

常见疑惑	深度解析
1. 怎么判断一道题到底能不能用贪心？	这是最难的。贪心算法没有固定的模板。实战技巧：举反例。如果你在脑海中想到了一个贪心策略，先试着给自己找茬，编造一个数据看看能不能推翻它。如果试了好几个极端情况都推翻不了，大概率就可以用贪心。如果随便一想就能举出反例（比如硬币找零的 [4,3,1]），立刻放弃贪心，转投动态规划。
2. 贪心算法的代码为什么通常都很短？	因为贪心算法本质上是常识逻辑的代码化。它不做深度的排列组合，不需要维护复杂的状态矩阵。通常就是**“排序 + 遍历 + O(1)的状态更新”**。所以如果一道困难题你用贪心写出了短短几行代码，你要么是绝对的天才，要么就是想简单了（掉入了局部最优的陷阱）。
3. 贪心可以解决背包问题吗？	分情况。对于**“0-1 背包”（物品不可分割，只能拿或不拿），贪心往往会失败，必须用动态规划。但对于“分数背包”**（物品可以切碎拿走一部分，比如金砂、面粉），贪心是完美的解法：算出每种物品的“性价比（单价）”，从高到低一直拿，直到背包装满即可。
4. 排序在贪心算法中的地位是什么？	核心前置动作。 90% 的贪心题目，第一步都是排序（按胃口大小、按结束时间、按单价等）。只有将数据变得有序，我们才能方便地执行“优先选择最大/最小/最早”的贪心策略。因此，贪心算法的时间复杂度往往被排序步骤主导，通常是 O(n log n)。