贪心算法

贪心算法的核心思想只有一句话：每一步都做当前看起来最优的选择，不回头、不反悔。如果这种"局部最优"能推导出"全局最优"，那就不需要回溯穷举，也不需要动态规划——贪心是最简洁高效的解法。

前置知识

贪心与回溯、动态规划的关系

贪心、回溯和动态规划，解决的其实是同一类"做选择"的问题，区别在于搜索空间的大小：

策略	搜索空间	核心思路	时间复杂度
回溯	穷举所有方案	选择 → 递归 → 撤销，暴力搜索	指数级
动态规划	穷举所有子问题（有重叠则缓存）	状态转移，避免重复计算	多项式级
贪心	每步只看一个最优选择	局部最优 → 全局最优	通常 O(NlogN) 或 O(N)

可以这样理解：回溯是暴力搜索所有分支，DP 是聪明地缓存重复分支，贪心则是直接砍到只剩一个分支。贪心之所以快，是因为它不需要比较多个选择——每一步的最优选择是确定的。

什么时候能用贪心？

贪心能正确工作的前提是问题具备贪心选择性质：每一步的局部最优选择，不会影响后续步骤达到全局最优。

这个性质没有通用的证明方法，通常靠以下方式判断：

1. 直觉验证：想一个贪心策略，然后试着构造反例。如果找不到反例，大概率可以贪心。
2. 交换论证：假设存在一个非贪心的最优解，证明可以通过"交换"调整为贪心解而不变差。
3. 经验识别：某些题型模式天然适合贪心（见下方决策树）。

关键判断：贪心还是 DP？

• 如果每一步的选择不影响后续选择的可行性 → 贪心
• 如果当前选择会约束后续可选范围，且存在多种组合方式 → DP
• 不确定时：先试贪心，举反例。有反例则转 DP

例如：[55] 跳跃游戏 可以贪心（只关心能到达的最远位置），但 [322] 零钱兑换 不能贪心（优先选大面额可能导致无解），必须用 DP。

---

解题决策树

拿到一道可能用贪心的题
│
├─ 涉及区间调度？（区间重叠/合并/选择）
│  └─ 按端点排序 + 贪心选择 .................. → 见「一」
│
├─ 涉及"跳跃/覆盖"类？（能否到达/最少步数）
│  └─ 维护当前可达最远位置 ................... → 见「二」
│
├─ 涉及序列上每步局部最优累积？（买卖股票/分发糖果）
│  └─ 逐步累积局部最优 ...................... → 见「三」
│
└─ 涉及任务调度/排列顺序优化？
   └─ 按某种优先级排序后贪心安排 ............. → 见「四」

---

一、区间调度问题

判断关键词：区间重叠、不重叠区间、合并区间、会议室。

适用场景：给定一组区间，求最多能选多少个不重叠的区间（或等价地，最少需要移除多少个区间使剩余不重叠）。

贪心策略：按结束时间升序排序，优先选结束最早的区间——因为结束越早，留给后续区间的空间越大。

为什么按结束时间而不是开始时间？因为我们的目标是"尽可能多地安排不重叠的活动"。一个结束得早的活动，即使开始得晚，也比一个结束得晚的活动更有利于后续安排。

function eraseOverlapIntervals(intervals: number[][]): number {
  // 按结束时间升序排序
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let end = -Infinity;

  for (const [start, finish] of intervals) {
    if (start >= end) {
      // 不重叠，选择该区间
      end = finish;
    } else {
      // 重叠，跳过（等价于移除）
      count++;
    }
  }

  return count;
}

题型参考（框架微调）：

题目	在区间贪心框架上的微调点
[435] 无重叠区间	标准框架，求最少移除数 = 总数 - 最多不重叠数。

二、跳跃/覆盖类问题

判断关键词：跳跃游戏、能否到达终点、最少跳跃次数、覆盖范围。

适用场景：数组中每个位置有一个"跳跃能力"，判断能否到达终点或求最少步数。

贪心策略：维护当前能到达的最远位置。遍历每个位置时更新最远覆盖范围，如果某个位置超出了当前最远覆盖，说明无法到达。

// 能否到达终点
function canJump(nums: number[]): boolean {
  let farthest = 0;

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

  return true;
}

求最少步数时，贪心策略升级为：在当前步能到达的范围内，找到下一步能跳最远的位置，相当于"步步取最远"。

function jump(nums: number[]): number {
  let steps = 0;
  let curEnd = 0;    // 当前这一步能到达的最远边界
  let farthest = 0;  // 在当前步范围内，下一步能到达的最远位置

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === curEnd) {
      // 到达当前步的边界，必须再跳一步
      steps++;
      curEnd = farthest;
    }
  }

  return steps;
}

题型参考（框架微调）：

题目	在跳跃贪心框架上的微调点
[55] 跳跃游戏	维护最远可达位置，判断是否覆盖终点。
[45] 跳跃游戏 II	在当前步边界内贪心取最远下一跳，统计步数。

三、序列累积类问题

判断关键词：买卖股票（不限次数）、最大利润、逐步累积。

适用场景：在序列上逐步做决策，每一步的最优选择可以独立于其他步。

贪心策略：把全局最优分解为每一步的独立局部最优，直接累加。

以 [122] 买卖股票的最佳时机 II（不限交易次数）为例：只要明天比今天贵，就今天买明天卖——每一段上涨区间的利润都不放过。

function maxProfit(prices: number[]): number {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    // 只要有上涨就吃下这段利润
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }

  return profit;
}

为什么贪心在这里是对的？因为任何一段跨多天的盈利 prices[j] - prices[i]，都等于中间每天涨幅之和 Σ(prices[k+1] - prices[k])。贪心吃下所有正涨幅，恰好等价于选择了所有盈利的交易区间。

注意：如果题目限制了交易次数（如最多 K 次），贪心就失效了，必须用 DP。

题型参考（框架微调）：

题目	在序列累积框架上的微调点
[122] 买卖股票的最佳时机 II	标准框架，累加所有正差值。

四、排序 + 贪心安排

判断关键词：任务调度、队列重建、按某种规则排列。

适用场景：需要按某种优先级/规则安排元素的顺序，排序后逐个贪心放置。

贪心策略：找到正确的排序依据，排序后按顺序处理——"先排序，再贪心"是这类问题的通用套路。难点在于确定排序的维度和方向。

// [406] 根据身高重建队列
// 贪心策略：先按身高降序排列（身高相同则按 k 升序），然后逐个按 k 值插入
function reconstructQueue(people: number[][]): number[][] {
  // 高个子先站好，矮个子后面插入不会影响高个子的 k 值
  people.sort((a, b) => b[0] - a[0] || a[1] - b[1]);

  const queue: number[][] = [];
  for (const person of people) {
    queue.splice(person[1], 0, person);
  }

  return queue;
}

以 [621] 任务调度器 为例，贪心策略是优先安排出现次数最多的任务——这样能最大程度利用冷却间隔，减少空闲时间。

题型参考（框架微调）：

题目	在排序贪心框架上的微调点
[406] 根据身高重建队列	身高降序 + k 值升序排列，再按 k 值逐个插入。
[621] 任务调度器	按出现频次排序，优先安排高频任务填充冷却间隔。

---

贪心 vs DP：如何判断？

这是贪心算法最核心的难点——很多题看起来可以贪心，但实际上需要 DP。以下是一些判断线索：

特征	倾向贪心	倾向 DP
每步选择是否独立	独立，不影响后续可选范围	相互约束，当前选择影响后续
是否存在"用小换大"的可能	不存在，局部最优就是全局最优	存在，短期亏损换长期收益
问题结构	每步只需一个最优选择	需要比较多种选择的组合效果

经典对比：

贪心可解	对应的 DP 变体（贪心失效）
[55] 跳跃游戏（能否到达）	[139] 单词拆分（不能只看最长匹配）
[122] 股票 II（不限次数）	[123] 股票 III（限 2 次，需要 DP）
[435] 无重叠区间（区间调度）	[1235] 规划兼职工作（区间带权，需要 DP）

实用策略：面对一道新题，先尝试贪心——想一个策略，举几个反例。如果找不到反例就贪心写；如果能构造出反例，说明局部最优不等于全局最优，转向 DP。

---

总结：解题速查表

题型	贪心策略	典型题目
区间调度	按结束时间排序，优先选结束早的	[435]
跳跃/覆盖	维护当前最远可达位置	[55] [45]
序列累积	逐步累加局部最优（正涨幅）	[122]
排序 + 贪心安排	找正确排序维度，贪心放置	[406] [621]