贪心
每一步做局部最优选择，并论证（或按题意信任）它能导向全局最优。代码继续用 JavaScript。
1. 贪心思想与适用条件
贪心不回溯试错：当前步选定后就不再反悔。
适用时通常具备：
- 贪心选择性质：局部最优可推出全局最优
- 最优子结构：最优解包含子问题的最优解
没有这两条就硬贪，容易错。实战里更多是：识别经典模型（区间、分配、霍夫曼那类），或「先写贪心再拿反例锤」。
常见套路：
- 排序后扫一遍
- 每次取当前最优候选（堆 / 优先队列）
- 维护一个「边界 / 余额」单调推进
2. 证明思路概览（交换论证 / 反证）
面试不必写正式证明，但要能讲清「为什么这么贪」。
交换论证
假设最优解与贪心解在某处不同 → 交换成贪心的选择后，结果不会变差 → 贪心也最优。
例：活动选择里「每次选结束最早的」——若最优解选了结束更晚的，换成结束更早的，腾出的时间只多不少，仍可行。
反证
假设贪心得不到最优 → 推出与题设或单调性矛盾。
实务
刷题时：先想「每一步唯一合理的倾向是什么」，再找反例；反例找不到且符合经典模型，再写代码。
3. 区间类问题
关键字：按端点排序，再贪心选取或合并。
活动选择 / 最多不重叠区间
每次选结束最早且与已选不冲突的区间。
// intervals: [[start, end], ...]，返回最多能选多少个不重叠区间
function maxNonOverlap(intervals) {
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 count
}
变形：「最少删除多少个区间使不重叠」= 总数 − 最多不重叠个数。
合并区间
按起点排序，能合并则扩右端。
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0])
const res = []
for (const [s, e] of intervals) {
if (!res.length || res[res.length - 1][1] < s) {
res.push([s, e])
} else {
res[res.length - 1][1] = Math.max(res[res.length - 1][1], e)
}
}
return res
}
用最少箭戳爆气球
按结束排序，一支箭覆盖尽可能多的重叠区间——与活动选择同构。
4. 分配 / 选择类问题
分发饼干
胃口小的优先用刚好够的饼干（两边排序 + 双指针）。
// g: 孩子胃口，s: 饼干尺寸，返回能满足的最大孩子数
function findContentChildren(g, s) {
g.sort((a, b) => a - b)
s.sort((a, b) => a - b)
let i = 0
for (let j = 0; j < s.length && i < g.length; j++) {
if (s[j] >= g[i]) i++
}
return i
}
跳跃游戏（能否到达）
维护「当前能跳到的最远下标」，扫到某处时若下标已超过最远 → 失败。
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])
}
return true
}
「最少跳几次」则在当前可达范围内再维护下一跳最远，分段贪心。
任务安排 / 找零钱（需条件）
部分找零问题在币值成倍数时可用贪心；否则可能要用 DP。分配类题目常「排序 + 每次给最急需的」。
5. 贪心失败的常见例子
| 直觉贪心 | 为何失败 |
|---|---|
| 背包：每次装性价比最高 | 0-1 背包物品不能拆，可能占满导致更优组合进不去 → 要用 DP |
| 最短路径：每次走当前最短边 | 一般图上不是全局最短（Dijkstra 有额外条件与证明） |
| 找零：总用最大面额 | 币制特殊时（如 1,3,4 找 6）贪心得 4+1+1，最优是 3+3 |
| 只看眼前收益最大 | 可能堵死后面更大收益（股票买卖次数限制等常要 DP） |
反例怎么找：构造「贪心吃掉关键资源后，剩余无法拼出更优解」。
// 0-1 背包：贪心按性价比会错的经典味道
// 容量 5；物品 A(价值5,重4)、B(价值3,重3)、C(价值3,重3)
// 性价比 A 最高 → 只装 A 得 5；最优 B+C 得 6
6. 与动态规划的区分
| 贪心 | 动态规划 | |
|---|---|---|
| 决策 | 每步只留当前最优，不回头 | 保留多种状态 / 子问题结果 |
| 正确性 | 依赖贪心选择性质 | 枚举或转移覆盖最优 |
| 典型 | 区间选择、跳跃最远、分发 | 背包、最长上升、路径计数 |
| 复杂度 | 常 O(n) / O(n log n) | 常 O(n²) / O(nW) 等 |
选型口诀：
- 能证明「每一步唯一不亏的选择」→ 贪心
- 当前选择影响后面，且要比较多种历史 → DP
- 拿不准时：先想反例；有反例就别硬贪
和回溯的关系：回溯试所有选择；贪心只走一条它认为对的路。