数学与贪心

贪心算法

贪心与动态规划的分界

动态规划要把所有选择都试一遍（靠备忘录避免重复）。 贪心跳过这一步：每一步直接选当下看起来最好的，选了就不回头。

所以贪心快得多（通常 O(n log n)，主要花在排序上），代价是它不总是对的。

贪心选择性质：局部最优的选择，一定能通向某个全局最优解。

这条性质成立才能用贪心。⚠️ 而它不能靠「试几个例子都对」来判断 —— 下面就有一个「试几个例子都对」的反例。

🚨 一个只差一枚硬币的反例

零钱兑换：用最少的硬币凑出目标金额。 直觉做法是「每次拿能拿的最大面额」。

const greedyCoins = (coins, amount) => {
  let n = 0, rest = amount;
  for (const c of [...coins].sort((a, b) => b - a)) {
    n += Math.floor(rest / c);
    rest %= c;
  }
  return rest === 0 ? n : -1;
};

实测对比动态规划的正确答案：

coins=[1,5,10,25]  amount=30    贪心 2   DP 2    ✅ 一致
coins=[1,3,4]      amount=6     贪心 3   DP 2    ❌ 贪心错
coins=[1,3,4]      amount=11    贪心 3   DP 3    ✅ 碰巧一致

amount=6 时贪心拿 4+1+1 三枚，而 3+3 只要两枚。

⚠️ 注意第三行：同一组面额，换个金额贪心又对了。 所以「我拿几个例子试过都没问题」完全说明不了问题 —— 这正是贪心最危险的地方。

⭐ 人民币和美元的面额体系恰好满足贪心性质（这是设计出来的）， 所以日常经验会误导你以为贪心总是对的。逐个金额穷举核对，没有一个反例：

面额体系                              金额 1~2000 上贪心 = 最优？
美元硬币 1/5/10/25 分                       ✅
美元 + 50 分 + 1 元                         ✅
人民币现行 1/5 角 + 1/5/10/20/50/100 元      ✅
人民币含 2 元 / 2 角（老版）                  ✅
欧元硬币 1/2/5/10/20/50 分                  ✅
对照：1/3/4                                 ❌ 最小反例 amount = 6

🚨 而「凑巧满足」有多凑巧：随机取 4 种含 1 的面额， 只有 8.2% 在 1~200 的金额上处处满足贪心。 👉 现实货币能让贪心成立是被设计成这样的，不是概率使然 —— 你在题目里遇到的面额十有八九不具备这个性质。

区间调度：贪心真正成立的经典场景

题意：一堆区间，选出最多的互不重叠的区间。

function maxNonOverlapping(intervals) {
  if (intervals.length === 0) return 0;
  // ⭐ 按【结束时间】排序，不是开始时间
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);

  let count = 1, end = sorted[0][1];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= end) { count++; end = sorted[i][1]; }
  }
  return count;
}

⭐ 为什么按结束时间排？ 结束得越早，留给后面的空间越多。 这句直觉就是它的证明骨架 —— 任何一个最优解里的第一个区间， 都可以换成「结束最早的那个」而不变差。

🚨 换成别的排序依据就错。实测三种排法在同一组区间上的结果：

区间 [[1,10], [2,3], [3,4], [4,5]]
  按结束时间排  →  3    ✅ 正确（[2,3] [3,4] [4,5]）
  按开始时间排  →  1    ❌ 先选了 [1,10]，把后面全挡住了
  按长度排      →  3    ✅ 这组碰巧对

⚠️ 「按长度排」在这组数据上是对的，换一组就不对了。 最小反例只要两个区间：

[[0,2], [2,3]]
  按长度排 → 先挑 [2,3]（长度 1），再看 [0,2]：0 >= 3 不成立，只能要 1 个
  最优           [0,2] 和 [2,3] 首尾相接，能要 2 个

🚨 而且「这组碰巧对」严重高估了它。5000 组随机区间的正确率：

按结束时间排   100.0%
按开始时间排    88.3%
按长度排        53.2%     ← 几乎是抛硬币

⭐ 注意上面那个四区间例子给人的印象正好反了：那组里按开始时间排最差（只有 1）， 按长度排看着挺好。放到随机数据上，按长度排才是三者里最差的。 👉 这恰恰说明问题：单个例子连“哪种错法更糟”都排不对序， 更不用说验证一种贪心成不成立。

跳跃游戏：贪心的另一种形态

题意：数组每个位置的值表示从那里最远能跳多远，问能否到达最后一个位置。

function canJump(nums) {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;              // 🚨 卡住了，到不了 i
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

⭐ 这里的「贪心」不是做选择，而是只维护一个量：目前能到达的最远位置。 不需要知道具体怎么跳过去的。

🚨 if (i > farthest) return false 必须在更新 farthest 之前。 放到后面的话，当前这一格自己的跳跃距离会先被算进去 —— 即使根本走不到这一格，也会误判成可达。

⚠️ 而这个错法的表现比「偶尔判错」更极端：它恒返回 true。 20000 组随机数组里一次都没返回过 false。

原因是纯算术的：更新之后 farthest ≥ i + nums[i] ≥ i（因为 nums[i] ≥ 0）， 所以 i > farthest 永远不可能成立，那一行等于没写。

[3,2,1,0,4]   正确 false   判断位置写错 → true

⭐ 于是「什么时候暴露」有个干净的答案：当且仅当正确答案是 false。 20000 组随机数组里正确答案为 false 的占 37.6% —— 不算罕见。 而这 7513 组无一例外在最后一格之前含有 0： 没有 0 挡路就不可能卡住，这也是为什么自测必须专门造一个带 0 的数组。

怎么判断能不能用贪心

按可靠性排序：

  1. 能证明贪心选择性质 —— 最可靠，但面试现场往往来不及
  2. 和暴力/DP 对拍 —— 写个小规模的 DP，随机数据跑几千组
  3. 说得出直觉 —— 「结束早的留空间多」这种。面试里够用
  4. ❌ 试几个例子 —— 上面两个反例说明了它有多不可靠

📌 面试里的实际打法：先说能不能贪心、给出直觉， 然后补一句「严格证明可以用交换论证：把最优解里的第一个选择换成贪心的选择， 不会变差」。这句话对绝大多数贪心题都成立，而且面试官想听的就是它。

⚠️ 拿不准的时候选 DP。贪心错了是答案错，DP 慢了只是慢 —— 代价不对称。

这一章到此为止

数学和贪心这两块都不在主依赖链上。剩下的 高频面试题是一份索引， 把前面所有章节按「题目长什么样」重新组织了一遍。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。