跳到主要内容

贪心算法

贪心算法（Greedy）是一种每步都选择"当前看起来最优"的策略，期望最终得到全局最优解的算法。它比 DP 更简单、更快（通常 O(n log n) 或 O(n)），但不是所有问题都能用贪心——只有满足"贪心选择性质"的问题才行。

核心思想​

贪心的本质是：在对问题求解时，总是做出在当前看来最好的选择，不回头、不尝试其他可能。这要求：

  1. 贪心选择性质：可以通过局部最优选择得到全局最优解。即每一步的选择独立于未来的选择。
  2. 最优子结构：问题的最优解包含子问题的最优解（与 DP 共享）。

与回溯/DP 的关键区别：回溯枚举所有可能，DP 通过子问题最优组合出全局最优，贪心只走一条路不回头。

何时能用贪心？​

判断一个题能否贪心是难点。常用判据：

  1. 尝试构造反例：能否找到一个局部最优导致全局非最优的例子？找不到就尝试证明。
  2. 交换论证：假设最优解与贪心解不同，证明可通过"交换"把最优解变成贪心解而不变差，从而贪心解也是最优。
  3. 排序后扫描：很多贪心题需要先排序，再按某种策略选。

实战中常见的提示词："最大化/最小化"、"求最少次数"、"能否到达"、"区间问题"。出现这些时优先想贪心，构造不出反例就上。

与 DP 的区别​

维度贪心DP
决策方式当前最优不回头枚举所有选择取最优
适用条件贪心选择性质 + 最优子结构重叠子问题 + 最优子结构
复杂度通常 O(n) 或 O(n log n)通常 O(n²) ~ O(n * m)
是否保证最优仅当贪心性质成立总是
典型题跳跃游戏、分发糖果背包、LIS、编辑距离

背包的反例：0-1 背包不能用贪心（按价值/重量比选）。比如物品 (w, v) 为 (2, 3), (3, 4), (4, 5)，容量 5。按 v/w 比：(2,3) 比 1.5 最大，先选它，剩余 3 容量选 (3,4)，总价值 7。但选 (3,4)+(4,5)... 容量 5 装不下两个，最是 (3,4)+(2,3) = 7。换例子 [(10, 60), (20, 100), (30, 120)] 容量 50：贪心选 (10,60) v/w=6，剩 40 容量，选 (20,100) v/w=5，剩 20 选不了 (30,120)，总 160。但选 (20,100)+(30,120)=220 才最优。这就是 0-1 背包必须用 DP 的原因。完全背包同样不能贪心。

经典题一：跳跃游戏（LC 55）​

判断能否从起点跳到终点，每个位置表示最大跳跃步数。

贪心策略：维护"当前能到达的最远位置" maxReach，遍历每个位置，若 i > maxReach 说明到不了，否则更新 maxReach = max(maxReach, i + nums[i])，到终点返回 true。

function canJump(nums: number[]): boolean {
  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 true;
}
  • 时间 O(n)，空间 O(1)
  • 贪心正确性：能到达 i 就能到达 i 之前所有位置，所以维护最远即可。

经典题二：跳跃游戏 II（LC 45）​

求跳到终点的最少步数。每步可以选择当前位置 1~nums[i] 范围内的任意目标。

贪心策略：每一步都尽可能跳到能到达更远的位置。维护当前步能到达的右边界 end 和下步能到达的最远 maxReach，到 end 时步数 +1 并更新 end。

function jump(nums: number[]): number {
  let steps = 0;
  let end = 0;     // 当前步能到达的右边界
  let maxReach = 0; // 下一步能到达的最远
  for (let i = 0; i < nums.length - 1; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);
    if (i === end) {
      steps++;
      end = maxReach;
      if (end >= nums.length - 1) break;
    }
  }
  return steps;
}
  • 时间 O(n)，空间 O(1)
  • 这题 DP 会超时（O(n * max(nums))），贪心是最优解。

经典题三：分发糖果（LC 135）​

n 个孩子各有评分，相邻孩子评分高的糖果更多，每人至少 1 颗，求最少糖果数。

贪心策略：两次遍历。从左到右保证比左边评分高的孩子糖果更多；从右到左保证比右边评分高的更多。取两次的 max。

function candy(ratings: number[]): number {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // 从左到右
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }
  // 从右到左
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }
  return candies.reduce((a, b) => a + b, 0);
}
  • 时间 O(n)，空间 O(n)（可优化到 O(1) 用上坡/下坡计数）
  • 贪心正确性：每个方向只考虑一个约束，两次取 max 同时满足两个约束。

经典题四：区间调度（LC 435 无重叠区间）​

给一组区间，求最少删除多少个使剩余不重叠。

贪心策略：按右端点排序，每次选右端点最小且不与上一个冲突的区间。直觉：右端点越小，留给后续的空间越大。

function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[1] - b[1]); // 按右端点排序
  let count = 1; // 不重叠区间数
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= end) {
      count++;
      end = intervals[i][1];
    }
  }
  return intervals.length - count; // 删除数 = 总数 - 保留数
}
  • 时间 O(n log n)（排序），空间 O(1)
  • 正确性证明（交换论证）：假设最优解不选右端点最小的区间 A 而选 B（B 右端点更大），可把 B 换成 A，A 右端点更小不与后续冲突，仍是最优。反复交换可得贪心解 = 最优解。

经典题五：合并会议室 / 射击气球（LC 452）​

用最少的箭射爆所有气球（气球用区间表示，箭射中区间即爆）。

贪心策略：按右端点排序，从左到右扫描，每次箭射在当前最右端点位置，能击穿所有起点 <= 该位置的气球。

function findMinArrowShots(points: number[][]): number {
  if (points.length === 0) return 0;
  points.sort((a, b) => a[1] - b[1]);
  let arrows = 1;
  let end = points[0][1];
  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > end) { // 不在当前箭范围
      arrows++;
      end = points[i][1];
    }
  }
  return arrows;
}

经典题六：分发饼干（LC 455）​

n 个孩子胃口 g[i]，m 块饼干大小 s[j]，饼干 >= 胃口才能满足，求最多满足多少孩子。

贪心策略：双指针 + 排序。小饼干先满足胃口小的孩子。

function findContentChildren(g: number[], s: number[]): number {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let i = 0, j = 0;
  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) i++; // 满足孩子 i
    j++; // 饼干用掉
  }
  return i;
}

经典题七：任务调度器（LC 621）​

给任务列表和冷却 n，相同任务需间隔 n 个时间单位，求最少时间。

贪心策略：安排出现次数最多的任务作为"骨架"，剩余空隙填其他任务。

function leastInterval(tasks: string[], n: number): number {
  const freq = new Map<string, number>();
  for (const t of tasks) freq.set(t, (freq.get(t) ?? 0) + 1);
  const maxFreq = Math.max(...freq.values());
  // 出现 maxFreq 次的任务数
  const maxCount = [...freq.values()].filter(v => v === maxFreq).length;
  // 框架长度：(maxFreq - 1) * (n + 1) + maxCount
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}
  • 时间 O(n)，空间 O(1)（任务种类有限）
  • 正确性：最高频任务决定最少时间，框架已是最优；任务数更多时直接填满空闲。

贪心常用技巧​

  1. 排序后扫描：区间问题、调度问题、双指针贪心。按起点或终点排序是关键。
  2. 优先队列（堆）：需要动态选最大/最小时，如合并 K 个有序链表、IPO 问题。
  3. 按维度贪心：分发糖果是"两次单维度贪心取 max"。
  4. 维护极值：跳跃游戏维护 maxReach。
  5. 从结果倒推：有时从结果（最大/最小）反推更容易，如"删 k 个数字使剩余数最大"用单调栈。

常见反例：贪心不适用的情况​

  1. 0-1 背包：上面已证，按 v/w 比选不保证最优。必须 DP。
  2. 找零钱（任意面值）：硬币 [1, 3, 4] 凑 6。贪心选最大 4，再选 1+1=3 枚，但 3+3=2 枚最优。常规贪心不适用，必须 DP（特殊币种如 1/5/10 才适用）。
  3. 最长递增子序列：朴素贪心（每次选更大的）会错。正确解是 DP 或二分贪心（维护 tails 数组）。
  4. 旅行商问题：贪心（最近邻）不保证最优，必须 DP 状态压缩或回溯。

如何证明贪心正确？​

面试中常被追问"为什么贪心对"。常用证明方法：

  1. 交换论证：假设最优解与贪心解不同，构造交换使最优解向贪心解靠拢且不变差。
  2. 数学归纳：证明前 k 步贪心与最优解一致。
  3. 反证法：假设贪心不是最优，导出矛盾。
  4. 构造下界：证明任何解都 >= 某下界，贪心解恰等于该下界。

复杂度对比​

题DP 解贪心解
跳跃游戏 IIO(n * max(nums))O(n)
分发糖果O(n²)O(n)
区间调度O(n²)O(n log n)
任务调度模拟 O(time)O(n)
跳跃游戏O(n²)O(n)

当 DP 超时、且能构造贪心策略时，优先贪心。

经典题目清单​

  • 跳跃类：LC 55 / 45
  • 区间类：LC 435 / 452 / 406（按身高重建队列）/ 763（划分字母区间）/ 56（合并区间）
  • 分配类：LC 135 / 455 / 621
  • 序列类：LC 402（移除 K 个数字）/ 321（拼接最大数）/ 659（分割为连续子序列）
  • 字典序：LC 316（去重使字典序最小）/ 402
  • 单调栈配合：LC 402 / 316 / 42（接雨水也可贪心双指针）

与其他算法结合​

  • 贪心 + 排序：几乎所有区间贪心都需要先排序。
  • 贪心 + 优先队列：动态选最值，如 LC 502 IPO、LC 630 课程表 III。
  • 贪心 + 单调栈：LC 402 移除 K 数字、LC 316 去重。
  • 贪心 + 双指针：LC 11 盛最多水、LC 881 救生艇。
  • 贪心 + 前缀和：LC 134 加油站。

面试技巧：

  • 看到"最少/最多/最少次数"且能想出局部最优策略 → 先试贪心，构造不出反例就上。
  • 写完贪心后主动说"我能想到的反例是…，但…不成立"，主动给出正确性论证更得分。
  • 实在想不出贪心，DP 是兜底——复杂度高但保证正确。