贪心算法

讲解

贪心算法每一步都取当前看起来最好的选择，指望局部最优的累积正好就是全局最优。它与 DP 的分水岭在于：DP 保留所有可能性、最后才拍板（枚举最后一次决策），贪心每一步就拍板、永不回头——所以贪心更快（通常 O(n log n)，瓶颈常在排序），但只对满足「贪心选择性质」的问题正确。用错的贪心是安静的错误：小测试全过、特定构造的数据才翻车。

贪心的难点不在代码（往往十几行），而在证明「为什么局部最优足够」。两个常用论证工具。交换论证：假设存在一个最优解与贪心解不同，证明把它的某一步换成贪心选择不会变差，逐交换下去最优解就变成了贪心解——分发饼干（最小胃口配最小能满足它的饼干）用它最顺手。反证 + 区间端点论证：区间调度选「结束最早」的区间，因为选结束晚的只会压缩后续空间，不可能更优。面试中不要求形式化证明，但主动给出一句直觉论证（「因为……所以换掉它不会更差」）是高分表现。

三道招牌菜定型手感。分发饼干：双排序 + 双指针，小饼干先满足小胃口，一次扫描。跳跃游戏：不模拟每一步怎么跳，只维护「目前能到达的最远下标」，遍历中持续刷新——当前位置超出最远可达即失败。无重叠区间：按右端点排序，贪心保留结束最早的，被丢弃的就是答案——它和「会议室安排」「射气球」是同构家族，识别信号是「区间 + 最多保留 / 最少移除」。

示例

分发饼干、跳跃游戏、无重叠区间：

import assert from 'node:assert/strict';

function findContentChildren(g, s) {
  g.sort((a, b) => a - b); // 胃口从小到大
  s.sort((a, b) => a - b); // 饼干从小到大
  let child = 0;
  for (const cookie of s) {
    if (child < g.length && cookie >= g[child]) child++; // 最小能满足的优先
  }
  return child;
}

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

// 按右端点排序，保留结束最早的，其余移除
function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let kept = 0;
  let end = -Infinity;
  for (const [start, finish] of intervals) {
    if (start >= end) {
      kept++;
      end = finish;
    }
  }
  return intervals.length - kept;
}

assert.strictEqual(findContentChildren([1, 2, 3], [1, 1]), 1);
assert.strictEqual(findContentChildren([1, 2], [1, 2, 3]), 2);

assert.strictEqual(canJump([2, 3, 1, 1, 4]), true);
assert.strictEqual(canJump([3, 2, 1, 0, 4]), false);
assert.strictEqual(canJump([0]), true);

assert.strictEqual(
  eraseOverlapIntervals([
    [1, 2],
    [2, 3],
    [3, 4],
    [1, 3],
  ]),
  1,
);
assert.strictEqual(
  eraseOverlapIntervals([
    [1, 2],
    [1, 2],
    [1, 2],
  ]),
  2,
);

console.log('贪心示例全部通过');

canJump 的「最远可达」视角值得回味：它不关心具体跳法（那是 DP 或回溯的思路），只维护一个标量——信息被压缩到极致，复杂度降到 O(n)。贪心解题常伴随这种「状态极简」的美感。

常见坑

• 凭直觉上贪心不验证：「看起来对」的贪心策略要用反例压力测试；能用 DP 解且数据规模允许时，贪心至少要有一个论证或大量对拍。
• 排序键选错：区间调度按右端点排，按左端点或长度排都有反例；写之前先想「哪个属性决定后续空间」。
• sort 不传比较函数：复习排序一章的坑——JS 默认按字符串排，数字数组必须 (a, b) => a - b。
• 跳跃游戏里模拟具体路径：逐跳模拟既慢又易错；维护最远可达下标即可，不要追踪路径。
• 边界忘记单元素：[0] 可达（已在终点）、[0, 1] 不可达——这类题首尾边界各测一例。

小结

贪心 = 每步局部最优且不回头；只对有贪心选择性质的问题成立；交换论证和端点论证是两个证明工具；代码常是排序 + 一次扫描。下一章进入位运算的紧凑世界。