经典贪心问题

基于通用算法套路 · 核于 2026-07

速查

• 活动选择 / 区间调度：n 个区间选最多互不重叠——按结束时间升序排序，第一个必选，之后每个 start ≥ 上个 end 就选。复杂度 O(n log n)。这是贪心的「Hello World」。
• 跳跃游戏 II（最少跳跃）：数组每个元素是该位置最大跳力，求到末尾最少几跳——维护「当前一跳能到的最远边界」，越过边界就再跳一次。O(n)，不排序。
• 分发糖果：每个孩子有评分，相邻评分高的糖更多——双向扫描：左→右保证「比左邻高分则糖多」，右→左取 max 保证「比右邻高分则糖多」。O(n)，是贪心的「两次扫描」范式。
• Huffman 编码：带权（频率）字符构造最优前缀编码树——贪心 + 优先队列：每次弹出两个最小频率节点合并，新节点入队，直至剩一棵树。O(n log n)。低频字符放深处（编码长），高频放浅处（编码短）。
• 任务调度（最大利润）：每个任务有截止时间和利润，每天做一个——按利润降序，每个任务抢占其截止时间最靠后的空闲槽（并查集加速找空闲槽）。
• Dijkstra 单源最短路：本质贪心——每轮从未确定点中选当前距离最小的确定下来（贪心选择性质：该最短距离不会再被更新）。O((V+E) log V)。
• Prim 最小生成树：从任一点出发，每轮**选「已选点集到未选点的最短边」**加入生成树。O(E log V)。
• Kruskal 最小生成树：按边权升序排序，逐条尝试加入（用并查集判不构成环）——排序 + 选择的标准贪心。O(E log E)。
• 分数背包：物品可分割，按单位价值降序，能装就装、装不下就切一部分装满——贪心成立。注意与 0-1 背包（不可分割，需 DP）区分。
• 共性：除跳跃游戏 / 分发糖果外，都是「排序 + 一个 for」；Dijkstra / Prim / Kruskal 是「大算法」，但内核都是贪心选择性质。
• 交互演示：快速排序可视化 —— 贪心依赖排序预处理。

一、活动选择 / 区间调度

n 个活动（区间）各有开始/结束时间，选出最多互不重叠的活动。这是贪心最经典的入门题。

贪心策略：按结束时间升序排序，选第一个（结束最早），之后每个不与上一个冲突就选。

function activitySelection(acts) {
  acts.sort((a, b) => a.end - b.end);     // 灵魂：按结束时间排序
  const res = [acts[0]];
  let lastEnd = acts[0].end;
  for (let i = 1; i < acts.length; i++) {
    if (acts[i].start >= lastEnd) {       // 不与上一个重叠
      res.push(acts[i]);
      lastEnd = acts[i].end;
    }
  }
  return res;                             // 最多不重叠活动
}

• 复杂度：排序 O(n log n) + 扫描 O(n) = O(n log n)。
• 为什么按结束时间：结束越早，给后面留的时间越多，能选的活动越多（交换论证证明，见策略与证明）。
• 变体：会议室分配（求最少会议室容纳所有会议 → 不再是选最多不重叠，而用最小堆维护结束时间）；射爆气球（区间选点覆盖）。

二、跳跃游戏 II（最少跳跃）

数组 nums，nums[i] 表示从 i 最多能跳到 i+nums[i]，求从 0 跳到末尾的最少跳跃次数（保证可达）。

贪心策略：维护「当前一跳能到达的最远边界 end」和「扫描过程中能到达的最远 maxReach」，越过 end 就再跳一次并把 end 更新为 maxReach。

function jump(nums) {
  let steps = 0, end = 0, maxReach = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);  // 扫描扩展最远可达
    if (i === end) {                             // 越过当前一跳的边界
      steps++;                                   // 再跳一次
      end = maxReach;                            // 边界更新为扫描到的最远
    }
  }
  return steps;
}

• 复杂度：O(n)，一次扫描，无需排序。
• 贪心直觉：在「当前一跳能覆盖的范围内」，找下一跳能达到的最远点——这是贪心地最大化每跳的覆盖范围。
• 对比：跳跃游戏 I（判断能否到达）更简单，维护 maxReach，扫描时若 i > maxReach 则不可达。

三、分发糖果

ratings 数组，每个孩子至少 1 颗糖，相邻孩子评分高的糖必须更多，求最少总糖数。

难点：约束是双向的（与左邻、右邻都要比），单一方向扫描无法同时满足。解法：双向扫描。

function candy(ratings) {
  const n = ratings.length;
  const c = new Array(n).fill(1);        // 每人先发 1 颗
  for (let i = 1; i < n; i++)             // 左 → 右：比左邻高分则糖多
    if (ratings[i] > ratings[i-1]) c[i] = c[i-1] + 1;
  for (let i = n - 2; i >= 0; i--)        // 右 → 左：比右邻高分则糖多（取 max）
    if (ratings[i] > ratings[i+1]) c[i] = Math.max(c[i], c[i+1] + 1);
  return c.reduce((s, x) => s + x, 0);
}

• 复杂度：O(n)，两次扫描。
• 贪心本质：每人在满足所有相邻约束下取最小糖数（贪心地只发必要的糖），两个方向扫描后取 max 保证双向约束同时满足。
• 关键：右→左扫描要 Math.max(c[i], c[i+1]+1)，不能直接覆盖（要保留左→右已满足的约束）。

四、Huffman 编码

给定字符及其频率，构造最优前缀编码（编码总长度最短，且无编码是另一个的前缀）。

贪心策略：频率小的字符编码长、频率大的编码短。用优先队列（最小堆）：每次弹出两个最小频率节点合并为新节点（频率 = 两者之和），新节点入队，直至队列剩一棵树。

function huffman(freqs) {                 // freqs: [{char, freq}]
  const heap = new MinHeap((a,b) => a.freq - b.freq);
  for (const f of freqs) heap.push({ freq: f.freq, char: f.char });
  while (heap.size > 1) {
    const a = heap.pop();                 // 最小频率
    const b = heap.pop();                 // 次小频率
    heap.push({ freq: a.freq + b.freq, left: a, right: b });  // 合并
  }
  return heap.pop();                      // 返回 Huffman 树根
}

• 复杂度：O(n log n)（n 个字符，每次合并 O(log n)，共 n-1 次）。
• 正确性：频率最小的两个字符必在最深处（编码最长），合并它们不影响其他字符的最优性（交换论证 + 归纳）。
• 应用：数据压缩（gzip、JPEG 等的熵编码阶段）。

五、Dijkstra / Prim / Kruskal：大算法的贪心内核

这三个图算法虽然「大」，但本质都是贪心——每步做当前最优选择且不回退。

Dijkstra 单源最短路（非负权）

每轮从未确定点中选当前距离最小的确定下来（贪心选择性质：该距离不会再被更新，因为后续路径只会更长），再用它松弛邻居。

重复 V 次：
  选「未确定 + 距离最小」的点 u（贪心选择）
  标记 u 已确定
  用 u 松弛其所有邻居（更新距离）

• 贪心成立前提：边权非负（若有负权，贪心选择性质不成立，需 Bellman-Ford）。

Prim 最小生成树

从任一点出发，维护「已选点集」，每轮**选「已选点集到未选点的最短边」**加入生成树（横切边中选最短，贪心）。

Kruskal 最小生成树

按边权升序排序，逐条尝试加入生成树，用并查集判不构成环——这是「排序 + 逐个选择」的标准贪心。

算法	贪心选择	复杂度
Dijkstra	未确定点中距离最小的	O((V+E) log V)
Prim	横切边中最短的	O(E log V)
Kruskal	边权升序逐条加（并查集判环）	O(E log E)

六、分数背包（贪心成立）

容量 W 的背包，物品有价值和重量且可分割，求最大价值。按单位价值降序，能装就装、装不下就切一部分装满。

function fractionalKnapsack(items, W) {  // items: [{v, w}]
  items.sort((a, b) => (b.v/b.w) - (a.v/a.w));  // 单位价值降序
  let total = 0;
  for (const it of items) {
    if (W >= it.w) { total += it.v; W -= it.w; }  // 整个装
    else { total += it.v * (W / it.w); break; }    // 切一部分装满
  }
  return total;
}

对比：0-1 背包（不可分割）单位价值贪心失效（见入门反例），需 DP。可分割与否是贪心成立的关键分水岭。

交互演示

• 快速排序可视化演示 —— 多数经典贪心（Kruskal、活动选择）依赖排序预处理

下一步

经典模型熟练后，回到参考速查贪心成立条件、代码模板、贪心 vs DP 对比与易错点，构建完整知识图谱。