贪心算法看起来像是一种"投机取巧"——每一步只挑当前最划算的选项，从不回头，居然最后能拿到全局最优。代码常常短得离谱，跑得也快。但贪心的真正难点不是写代码，而是判断这道题到底允不允许贪心。同样一个 argmax 循环，在跳跃游戏上完全正确，在 {1, 3, 4} 找零上就会给出错误答案。

本文按照"先讲清楚贪心为什么对、再讲什么时候不能用、最后用一组经典题打通直觉"的顺序，把贪心算法讲一遍。涉及的题目包括：跳跃游戏 I/II、加油站、买卖股票的最佳时机 II、无重叠区间、任务调度器、划分字母区间。

系列导航

📚 LeetCode 算法精讲系列（共 10 篇）：

1. 哈希表（两数之和、最长连续序列、字母异位词分组）
2. 双指针技巧（对撞指针、快慢指针、滑动窗口）
3. 链表操作（反转、环检测、合并）
4. 滑动窗口技巧
5. 二分查找
6. 二叉树遍历与构造（前中后序、层序、构造）
7. 动态规划入门（一维/二维 DP、状态转移）
8. 回溯算法（排列、组合、剪枝）
9. → 贪心算法 ← 当前文章
10. 栈与队列（括号匹配、单调栈）

贪心到底是什么

贪心算法（Greedy Algorithm）：每一步都按照某个"局部最优"标准做出选择，选完不再回头修改，最终希望得到全局最优解。

“不回头"是贪心和回溯、DP 最关键的区别——没有 undo，没有备选状态表。这个特性带来两个后果：跑得飞快（通常 $O(n)$ 或 $O(n\log n)$），但正确性必须证明。

要让"局部最优 → 全局最优"这件事成立，问题必须满足两条性质：

• 贪心选择性质（Greedy Choice Property）：存在一种局部最优的选择，它一定是某个全局最优解的一部分。换句话说，做出这个选择后，“还能拿到全局最优"的可能性没有被破坏掉。
• 最优子结构（Optimal Substructure）：做出这一步选择后，剩下的问题本身也是同类问题的一个更小实例，且子问题的最优解能和当前选择拼成原问题的最优解。

最优子结构其实大部分问题都满足，真正"难"的是贪心选择性质——它需要证明。如果你不能证明贪心选择性质，那你写出来的就不是贪心算法，而是一个猜测。

贪心 vs 动态规划 vs 回溯

贪心的本质是**“用证明换运行时”**：你在算法分析阶段多花精力，换取代码上的极简和运行时上的线性。

当贪心失效：硬币找零的反例

硬币找零是讲贪心时绕不开的反例。在标准美元硬币集合 {1, 5, 10, 25} 上，“每次拿不超过剩余金额的最大硬币"对任何金额都是最优的。但只要把硬币集合改成 {1, 3, 4}、目标金额改成 6，同样的贪心策略会给出 4 + 1 + 1（三枚硬币），而最优解是 3 + 3（两枚）。

算法没变，直觉没变，错的是问题结构——后一种硬币集合不满足贪心成立所需的代数性质（严格来讲，它不构成一个 matroid）。

记住这个反例，因为它是判断"我现在能不能贪"的最快试金石：贪心是否正确，是问题本身的属性，不是算法的属性。

贪心策略的常见套路

LeetCode 上的贪心题大致就这么几类骨架：

• 按结束时间排序：区间调度（无重叠区间、最少箭、合并区间的多种变体）
• 按开始时间排序：会议室分配
• 按比值/价值密度排序：分数背包、加权调度
• 维护运行极值：跳跃游戏（max_reach）、买卖股票 I（min_price）、最大子数组（max_ending_here）
• 前缀和遇负重置：加油站、Kadane 算法、划分字母区间
• 按频率/堆调度：任务调度器、重构字符串
• 两次扫描的局部调整：分发糖果、摆动序列

后面的题目几乎都能往这些骨架里套。能识别套路，题就解了一大半。

怎么证明贪心是对的：交换论证

交换论证（Exchange Argument） 是贪心证明的万能模板：

1. 任取一个最优解 OPT。
2. 找到 OPT 中第一个"不符合贪心策略"的选择，把它替换成贪心选择，得到新解 OPT'。
3. 证明 OPT' 不会比 OPT 差——大小相同、可行性保持。
4. 反复进行这个替换过程，最终就把 OPT 改造成了贪心算法的输出。
5. 既然贪心解和某个最优解大小相同，贪心解就是最优解。

以区间调度为例：假设 OPT 的第一个区间是 X = [1, 7)，而贪心的选择是结束最早的 G = [2, 5)。因为 G.end ≤ X.end，所有原本和 X 兼容的后续区间也一定和 G 兼容。把 X 换成 G，区间数目不变、互不冲突也保持，得到新解 OPT'。再对第二个、第三个选择重复同样的论证，最终贪心策略产出的方案大小等于 OPT，即最优。

跳跃游戏 II、任务调度器的下界、几乎所有"挑最早结束/挑最大跨度"的贪心题，都用这个模板证明。

LeetCode 55: 跳跃游戏

给定非负整数数组 nums，nums[i] 是从位置 i 出发能跳的最大步数。从下标 0 出发，判断能否到达最后一个下标。

示例：[2,3,1,1,4] → true，[3,2,1,0,4] → false。

贪心洞察

我们其实不需要知道"具体怎么跳”，只需要知道"到目前为止能到达的最远下标是多少”。维护一个变量 max_reach，从左到右扫；如果某个时刻 i > max_reach，说明 i 这个位置根本到不了，提前返回 false。

左图是 [2,3,1,1,4]，i=1 时 max_reach 直接跳到 4，已经覆盖终点。右图是 [3,2,1,0,4]，下标 3 的 0 把 max_reach 钉死在 3，下一步 i=4 > max_reach=3，宣告失败。

为什么贪心是对的

证明几乎是"显然的”：如果位置 i 可达，那么 [0, i + nums[i]] 内的每个位置都可达（直接从 i 跳过去）。max_reach 就是把所有这种区间合并起来，等于"目前所有可达位置的最大值"。也就是说，max_reach 不是一个估计量，它精确地等于全局可达范围。局部更新等价于全局信息。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """O(n) 时间，O(1) 空间。"""
        max_reach = 0
        n = len(nums)
        for i, step in enumerate(nums):
            if i > max_reach:           # 当前位置不可达
                return False
            max_reach = max(max_reach, i + step)
            if max_reach >= n - 1:      # 提前返回：终点已纳入射程
                return True
        return True

常见坑：

• 忘了 i > max_reach 检查就更新 max_reach。这种写法对 [0, 1] 都会返回错误的 True，因为它默认你"理应"在每一个 i 上。
• 提前返回写成 max_reach == n - 1。注意 max_reach 可能一次性远超终点，必须用 >=。

LeetCode 45: 跳跃游戏 II

与 LC 55 相同，但保证可达，求最少跳跃次数。

把跳跃看作 BFS 的层：第 1 跳能到的范围是 [1, nums[0]]；第 2 跳能到的范围是"从第 1 跳的任意位置再跳一次"能覆盖的最远点；以此类推。我们不需要真的开 BFS 队列——只要记住"当前层的右边界"和"下一层能延伸到的右边界"就够了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def jump(self, nums: List[int]) -> int:
        """
        贪心 BFS：O(n) 时间，O(1) 空间。

        - current_end：当前已"承诺"的这一跳能到达的最远下标。
        - farthest：从当前层任意位置出发，下一跳能延伸到的最远下标。
        - i 走到 current_end 时必须再消耗一次跳跃，下一层范围就是 farthest。
        """
        jumps = 0
        current_end = 0
        farthest = 0
        for i in range(len(nums) - 1):       # 终点本身不需要再起跳
            farthest = max(farthest, i + nums[i])
            if i == current_end:             # 当前层走完了
                jumps += 1
                current_end = farthest
                if current_end >= len(nums) - 1:
                    break
        return jumps

最优性论证：在所有"经过 k 跳能到的位置"中，挑 i + nums[i] 最大的那个作为跳板，永远不亏——任何用了"跨度更短的跳板"的最优解，都可以通过交换论证替换成"跨度最大的跳板"而不增加总跳数。所以始终扩张 farthest 是安全的。

LeetCode 134: 加油站

环形路上有 n 个加油站，第 i 站有油 gas[i] 升，从站 i 到站 i+1 耗油 cost[i] 升。油箱容量无限、起始为空，求能完成一圈的起点编号；不存在则返回 -1。题目保证解唯一。

两条决定算法的事实

1. 可行性判定：解存在当且仅当 sum(gas) >= sum(cost)。如果总油量都不够总消耗，没有任何起点能补上这个缺口。
2. 起点定位：定义 Δ[i] = gas[i] - cost[i]，从站 0 出发计算前缀和。最优起点 = 前缀和取得全局最小值的那个位置的下一个。

图中数据是 gas = [1,2,3,4,5]、cost = [3,4,5,1,2]。前缀和在"经过站 2 之后"达到全局最低 -6，所以从站 3 出发最稳妥：站 3 和站 4 的盈余 +3 + +3 = +6 正好补上前面的亏空，绕回起点时油箱归零。

为什么遇负重置就够了

假设我们试探性地从下标 s 出发，走到下标 j 时油箱负了。那么**[s, j] 中的任何一个下标都不可能是合法起点**：从 s 出发到 j 之前累计油量都还非负，换成更靠后的起点 s' ∈ (s, j] 时，到 j 时反而拥有更少的油，肯定也会失败。下一个值得尝试的起点只能是 j + 1。整个过程中每个站点最多被扫两次（一次"试探累计"、一次"重置后重新累计"），总共 $O(n)$。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        """O(n) 时间，O(1) 空间。"""
        total_tank = 0      # 全局可行性
        current_tank = 0    # 从候选起点出发的累计
        start = 0
        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total_tank += diff
            current_tank += diff
            if current_tank < 0:
                start = i + 1     # [start, i] 全部出局
                current_tank = 0
        return start if total_tank >= 0 else -1

LeetCode 122: 买卖股票的最佳时机 II

给定每日股价数组，可以多次买卖（任意时刻最多持有一股），求最大收益。

把问题翻译成"求所有正涨幅之和"

最优收益等于 Σ max(0, prices[i] - prices[i-1])：抓住每一个"今天比昨天贵"的差额，跳过所有下跌日。完全不需要识别波峰和波谷的位置。

为什么是对的？ 任何"低买高卖"的一对 (p_lo, p_hi)，都可以拆成相邻日差的电信和：

这个和里如果包含负数项，去掉它们一定让结果更大。所以最优策略就是只取所有正项；而每个正的日差都可以独立兑现（前一天卖、第二天再买，因为题目允许同一天卖完再买）。

1
2
3
4
5
6
7
8
9

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """O(n) / O(1)：所有正的日涨幅相加。"""
        return sum(
            max(0, prices[i] - prices[i - 1])
            for i in range(1, len(prices))
        )

注意：这个套路只适用于"无限次交易"的 LC 122。**LC 121（只交易一次）、LC 123 / 188（限定 k 次）**都不满足贪心选择性质——多次买卖会互相干扰——必须用 DP 解。

LeetCode 435: 无重叠区间

给定区间集合，求至少需要移除多少个区间，才能让剩下的区间互不重叠。

这本质上是活动选择问题的变形：先求最多可保留的互不重叠区间数 k，答案就是 n - k。

策略

按结束时间升序排序。从左往右扫，每次若当前区间起点 ≥ 上一个保留区间的终点，就保留它。

图中 11 个区间按结束时间排序后，贪心保留 [1,4)、[5,7)、[8,11)、[12,16) 这 4 个，其余每个都和这 4 个之一冲突，必须移除。

为什么是"最早结束"，不是"最早开始"或"最短"

• 按起点排序会被一个超长区间锁死：反例 [[1,10],[2,3],[4,5]]，按起点选 [1,10] 后再也选不出别的，但最优是删 [1,10] 保留另两个。
• 按长度排序也会失败：反例 [[1,5],[4,6],[5,10]]，最短的是 [4,6]（长度 2），选了它就把左右两个都挤掉了，反而比选 [1,5] 和 [5,10] 差。
• 按终点排序用前面的交换论证可以证明最优：把 OPT 的第一个选择换成"结束最早"的那个，可行性和数目都不变。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """O(n log n) 排序 + O(1) 额外空间。"""
        if not intervals:
            return 0
        intervals.sort(key=lambda iv: iv[1])
        kept = 1
        last_end = intervals[0][1]
        for s, e in intervals[1:]:
            if s >= last_end:    # 端点重合不算重叠
                kept += 1
                last_end = e
        return len(intervals) - kept

坑：判定写成 >=（不是 >）。本题把 [1,2] 和 [2,3] 视为不重叠。LC 452（用最少箭引爆气球）的语义相反，那里要用严格 >。

LeetCode 621: 任务调度器

字母数组代表任务种类，相同任务之间必须间隔至少 n 个冷却槽（任意其它任务或 idle 都行）。求最短调度长度。

公式化的下界

设 f_max 是出现频率最高的任务次数，k 是与 f_max 并列最高频的任务种数。答案是：

max(len(tasks), (f_max - 1) * (n + 1) + k)

怎么想出来的？ 把最高频任务摆成一个 n+1 列的表格：前 f_max - 1 行每行都是满的（长度 (f_max-1)*(n+1)），最后一行恰好放下并列最高频的 k 个任务。其余任务都可以塞进上面那些空格里，绝不会破坏冷却约束。如果填得下，调度长度就是上面这个公式；如果任务太多塞不下，那一个 idle 都不用，答案就是 len(tasks) 本身。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        """O(N) 时间（N = len(tasks)），O(1) 空间（字母表 ≤ 26）。"""
        counts = Counter(tasks).values()
        f_max = max(counts)
        k = sum(1 for c in counts if c == f_max)   # 并列最高频的任务数
        return max(len(tasks), (f_max - 1) * (n + 1) + k)

为什么不用堆：堆模拟（O(N log 26)）也能做，是面试常考的等价解法。但理解了"网格摆放"的论证后，闭式公式更优雅，而且能立刻得出 max(len(tasks), ...) 这个结论。

LeetCode 763: 划分字母区间

把字符串划分成尽可能多的段，使得同一字母只出现在同一段中。返回每段长度。

贪心洞察

先记录每个字母最后一次出现的位置 last[ch]。从左往右扫，维护当前段的右端点 end = max(end, last[s[i]])。当 i 走到 end 时，说明当前段里出现过的所有字母的最后一次出现都已经被覆盖，当前段可以收尾。

之所以贪心：每一步我们都把当前段扩展到"能容纳目前所有出现过的字母"的最小右端点——再早收尾会把某个字母切到两段；再晚收尾则浪费字符。两边都是最坏，正中间唯一。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        """O(n) 时间，O(1) 空间（字母表 ≤ 26）。"""
        last = {ch: i for i, ch in enumerate(s)}
        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        return result

手算示例（s = "ababcbacadefegdehijhklij"）：

最后出现位置：a→8, b→5, c→7, d→14, e→15, f→11, g→13,
              h→19, i→22, j→23, k→20, l→21
i=0..8   end 始终是 8 → 段 "ababcbaca"   长度 9
i=9..15  end = 15      → 段 "defegde"     长度 7
i=16..23 end = 23      → 段 "hijhklij"    长度 8
结果: [9, 7, 8]

总结

真正应该内化的几点

1. 贪心的正确性是结构性的，不是审美性的。 同一个 argmax 循环在跳跃游戏上是对的，在 {1, 3, 4} 找零上是错的。下手之前先识别结构——交换论证是否成立？是否符合 matroid？前缀和是否单调？——确认了再写。
2. 排序排在正确的键上。 区间调度按终点，分数背包按比值。键选错，算法看起来很合理，结果完全不对。
3. 维护一个不变量，而不是一条路径。 跳跃游戏的 max_reach、加油站的 current_tank、买卖股票 II 的日差——它们都是滚动聚合，而不是路径重建。贪心节省空间的奥秘就在这里。
4. 交换论证是核心证明工具。 把模板背下来，下次遇到"挑最早 X / 挑最大 Y"的新题，直接套。

题目分类速查

常见错误

• 凭"看起来合理"挑排序键（按起点、按长度），从不验证。
• 跳跃游戏忘了写 i > max_reach 检查，让算法在不可达位置上更新聚合量。
• 把 LC 122 的解法套到 LC 121/123/188 上——后者必须用 DP。
• 端点重合的处理：LC 435 用 >=，LC 452 用 >，混了就错。

不确定时先用一个对抗性的小样例（往往 n ≤ 5 就够）跑一下再相信你的贪心。如果找不出反例、又能勾勒出交换论证，那基本就是稳的。

常见问题 Q&A

怎么判断一道题能不能用贪心？

满足两条性质就能考虑——存在一个局部最优选择属于某个全局最优解（贪心选择性质），且做出选择后剩余问题仍是同类问题（最优子结构）。如果这两条都没法验证，就别贪。

贪心和 DP 该怎么取舍？

能贪一定贪，因为贪心通常 $O(n)$ 或 $O(n\log n)$，DP 至少 $O(n^2)$。但贪心需要严格证明——证明不出来就老老实实写 DP。LeetCode 上经常出现"看起来能贪、其实必须 DP"的题（最经典的就是 LC 322 找零）。

为什么区间调度按终点排序而不是起点？

按起点排序会让一个超长区间挤掉很多短区间。按终点排序的本质是"留给后面最多的空间"，并且能用交换论证严格证明最优。

跳跃游戏只维护最远距离够吗？

够。题目只问"能不能到"，不问"怎么到"。max_reach 精确等于"到目前为止所有可达位置的并集的右端点"，所以局部更新等价于全局信息。

加油站为什么"总油量够就一定有解"？

总油量 >= 总消耗意味着环上有正的盈余。如果某个起点中途断油，说明前缀和到那一点是负的；从下一站重新出发时，由于总盈余 >= 0，后面的累积一定能补上之前的亏损，绕一圈回到起点时油箱归零。

贪心一定要先排序吗？

不一定。区间调度需要排序；跳跃游戏、加油站、买卖股票 II 都是单次扫描，无需排序。关键是找到合适的贪心策略。

怎么证明贪心是对的？

常用三招——

• 反证法：假设有更优解 OPT，推出矛盾。
• 交换论证：证明把 OPT 中的第一个非贪心选择换成贪心选择不会让结果变差。
• 归纳法：证明每一步贪心选择后子问题规模缩小且最优性保持。

贪心算法的时间复杂度通常多少？

不需要排序的 $O(n)$（如跳跃游戏、加油站、买卖股票 II），需要排序的 $O(n\log n)$（如区间调度、合并区间）。比 DP（$O(n^2)$ 起步）和回溯（指数级）快得多。

至此 LeetCode 算法精讲系列全部完成。从哈希表到贪心，反复出现的元技巧只有一条：先识别问题的结构性质，再选择前提条件匹配的算法。Good luck。