LeetCode（九）：贪心算法

贪心算法乍一看像是在“偷懒”——每一步都选眼前最划算的选项，从不回头调整，最后居然还能得到全局最优解。代码通常短小精悍，运行效率也很高。但贪心真正的难点在于判断一个问题到底能不能用贪心解决。同样的一个 argmax 循环，在跳跃游戏里完全正确，换到 {1, 3, 4} 的找零问题上却会给出错误答案。

这篇文章的思路是先讲清楚贪心为什么能奏效和什么时候会失效，再通过一组经典题目帮助大家建立直觉。涉及的题目包括：跳跃游戏 I/II、加油站、买卖股票的最佳时机 II、无重叠区间、任务调度器、划分字母区间。

贪心算法到底是什么#

贪心算法（Greedy Algorithm） 的核心思想是每一步都选当前看起来最优的选项，选完后不再更改，最终希望这些局部最优能拼成全局最优解。

它和回溯、动态规划（DP）最大的区别在于“不回头”，没有撤销操作，也没有记录备选状态的表格。这种特性让贪心算法运行飞快（通常是 $$O(n)$$ 或 $O(n\log n)$ ），但代价是——正确性必须严格证明。

要让“局部最优”最终通向“全局最优”，问题需要满足两个关键性质：

贪心选择性质（Greedy Choice Property）：某个局部最优的选择一定是某个全局最优解的一部分。换句话说，做出这个选择后，未来仍有机会达到全局最优。
最优子结构（Optimal Substructure）：一旦做出这一步选择，剩下的问题会变成一个规模更小的同类问题，子问题的最优解可以和当前选择组合成原问题的最优解。

大部分问题其实都能满足最优子结构，真正难的是贪心选择性质——这是贪心算法成立的关键，也是最容易出错的地方。如果你无法证明贪心选择性质，那么你的算法顶多是个猜测，而不是一个可靠的贪心解法。

贪心 vs 动态规划 vs 回溯#

性质	贪心	动态规划	回溯
决策方式	选局部最优	枚举所有，取最优	枚举所有，剪掉不可行解
是否撤销	不撤销	不涉及（状态表记录所有）	回溯时撤销
时间复杂度	$$O(n)$$ 或 $O(n\log n)$	$$O(n^2)$$ ~ $O(n\cdot k)$	指数级
必备结构	贪心选择 + 最优子结构	最优子结构 + 重叠子问题	解可验证性
证明负担	高（需严格证明正确性）	低（转移方程 + 初值即可）	无（穷举天然正确）

贪心算法的核心在于**“用分析换效率”**：前期花时间证明算法的正确性，换来的是代码简洁和运行高效。

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

硬币找零问题，是贪心算法最经典的反面教材。用标准美元硬币 {1, 5, 10, 25} 找零时，每次选不超过目标金额的最大硬币，总能得出最优解。但只要稍微改动一下硬币集合，比如改成 {1, 3, 4}，目标金额设为 6，贪心策略就会出问题：它会给出 4 + 1 + 1（三枚硬币），而实际上最优解是 3 + 3（两枚）。

算法没变，思路也没变，问题出在问题本身的结构上。后一种硬币集合不满足贪心成立所需的数学性质（严格来说，它不是一个 matroid / 拟阵）。

这个例子值得牢记，因为它是检验贪心是否可行的最佳试金石：贪心算法的正确性，取决于问题本身的特性，而不是算法本身的设计。

贪心策略的常见套路#

在 LeetCode 上，贪心题的解法基本可以归为几类固定的模式：

按结束时间排序：比如区间调度问题，包括无重叠区间、最少箭、合并区间等变种。
按开始时间排序：例如会议室分配问题。
按比值或价值密度排序：像分数背包问题、加权调度问题。
维护运行时极值：比如跳跃游戏中的 max_reach、买卖股票 II 中的 min_price、最大子数组中的 max_ending_here。
前缀和遇负重置：典型例子有加油站问题、Kadane 算法、划分字母区间。
基于频率或堆的调度：如任务调度器、重构字符串。
两次扫描进行局部调整：比如分发糖果、摆动序列。

后面的题目几乎都能套进这些模式。识别出问题对应的模式，解题就完成了一大半。

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

贪心算法的正确性通常靠交换论证来证明。这个方法的核心思想很简单：通过一步步替换，把任意最优解“改造”成贪心解，同时保证每一步都不损失最优性。

具体步骤如下：

假设存在一个最优解 OPT。
找到 OPT 中第一个不符合贪心策略的选择，用贪心选择替换它，得到新解 OPT'。
证明替换后的新解 OPT' 至少和原解一样好——区间数不变、可行性保持。
不断重复这个过程，最终将 OPT 转化为贪心算法生成的解。
因为贪心解和某个最优解等价，所以贪心解也是最优的。

举个例子，比如区间调度问题：假设 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，说明当前位置根本无法到达，直接返回 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 就是把这些区间逐步合并的结果，它精确表示了当前所有可达位置的最大值。换句话说，局部更新完全等价于全局状态。

实现代码#

 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 跳能覆盖更远的范围；依此类推。我们不需要真的用队列实现 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。题目保证解唯一。

算法背后的两条关键事实#

可行性条件：只有当 sum(gas) >= sum(cost) 时，问题才有解。如果总油量不足以覆盖总消耗，任何起点都无法完成一圈。
确定起点：定义 Δ[i] = gas[i] - cost[i]，从前缀和的角度看，最优起点是前缀和达到全局最小值的位置的下一个站点。

以 gas = [1,2,3,4,5] 和 cost = [3,4,5,1,2] 为例。前缀和在经过站 2 后降到最低点 -6，因此从站 3 出发最合适：站 3 和站 4 的盈余 (+3) + (+3) = +6 恰好弥补前面的亏空，最终回到起点时油箱刚好归零。

为什么“遇负重置”有效#

假设我们尝试从下标 s 出发，走到下标 j 时油箱耗尽（current_tank < 0）。此时可以断定，区间 [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#

给定一个每日股价数组，允许不限次数地买卖股票（但任意时刻最多只能持有一股），求最大收益。

转换思路：累加所有上涨日的涨幅#

这个问题的核心在于抓住每一天比前一天价格上涨的部分，忽略下跌的日子。最优解就是把所有正的日涨幅加起来，完全不需要费劲去找最低点和最高点。

p_{hi} - p_{lo} = \sum_{i=lo+1}^{hi} (p_i - p_{i-1})

如果在这段区间里有下跌的日子（即负值项），去掉这些负值只会让总利润更大。因此，最优策略就是只保留所有正的日涨幅。而且因为题目允许同一天卖完再买，每个正的日涨幅都可以独立兑现。

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 （限定交易次数），就不满足贪心选择性质了——多次买卖会互相影响，必须用动态规划（DP）来解决。

LeetCode 435 —— 无重叠区间#

给定一组区间，求最少需要移除多少个区间，才能使剩下的区间互不重叠。

这其实是经典的活动选择问题的变种：先找出最多能保留的互不重叠区间数 k，答案就是总区间数减去 k，即 n - k。

解题思路#

按结束时间从小到大排序，然后从左往右扫描。每次遇到一个区间的起点 ≥ 上一个保留区间的终点时，就保留这个区间。

图中展示了 11 个区间按结束时间排序后的结果。贪心算法依次保留了 [1,4)、[5,7)、[8,11) 和 [12,16) 这 4 个区间。其余每个区间都与这 4 个中的某一个冲突，因此必须移除。

为什么选“最早结束”而不是“最早开始”或“最短”#

按起点排序容易被长区间卡住。比如反例 [[1,10],[2,3],[4,5]]，如果选了 [1,10]，后面就再也选不了别的区间了，但最优解是删掉 [1,10]，保留 [2,3] 和 [4,5]。
按长度排序也不靠谱。比如反例 [[1,5],[4,6],[5,10]]，最短的区间是 [4,6]（长度 2），选了它会导致左右两个区间都被挤掉，反而不如直接选 [1,5] 和 [5,10]。
按结束时间排序可以用交换论证证明是最优的：把任何最优解的第一个区间换成“结束最早”的那个，既不会破坏可行性，也不会减少保留的区间数。

实现代码#

 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 个冷却时间（可以是其他任务或空闲）。求完成所有任务所需的最短时间。

贪心下界公式#

设 f_max 是出现次数最多的任务的频率，k 是与 f_max 相同频率的任务种类数。答案可以直接用公式计算：

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

直观理解：把最高频任务按 n+1 列排成网格。前 f_max - 1 行每行都填满（长度为 (f_max-1)*(n+1)），最后一行放并列最高频的 k 个任务。其余低频任务可以填充到网格的空位中，不会违反冷却约束。如果所有任务都能塞进网格，调度长度就是公式结果；如果任务太多塞不下，那就直接返回任务总数 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"）：

1
2
3
4
5
6
最后出现位置：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]

真正应该记住的几点#

贪心算法的正确性靠的是结构，不是直觉。 同样的 argmax 逻辑，用在跳跃游戏上没问题，用在 {1, 3, 4} 的找零问题上就错了。动手之前，先搞清楚问题是否满足交换论证、拟阵性质或者前缀和单调性等结构性条件。
排序要选对关键属性： 区间调度按结束时间排，分数背包按单位价值排。选错了排序依据，代码可能看起来合理，但结果完全不对。
维护一个全局不变量，而不是具体路径。 比如跳跃游戏里的 max_reach、加油站问题里的 current_tank、买卖股票 II 的每日差值——这些是滚动更新的全局状态，而不是一步步回溯的路径。贪心算法的空间效率正是来源于此。
交换论证是最常用的证明工具。 记住它的套路：假设最优解，逐步替换为贪心选择，证明结果不劣于原解。遇到“最早 X”或“最大 Y”这类问题时，直接套用这个模板就行。

题目分类速查#

套路	LeetCode	贪心键	证明方法
区间调度	435, 452, 56	按结束时间排序	交换论证
可达性边界	55, 45	维护 `max_reach`	不变量归纳
前缀和重置	134, 53	遇负则重置	总和引理
日差捕获	122	累加正涨幅	分段拆解
频率布局	621	最高频优先公式	网格填充分析
末次出现扫描	763	扩展 `end` 至 `last[ch]`	最小分割引理
贪心失效的反面教材	322	贪心 ≠ 最优	必须用 DP

常见错误#

挑排序键时只凭直觉（比如按起点或长度），懒得验证是否正确。
写跳跃游戏时漏了 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。

贪心算法到底是什么#

贪心 vs 动态规划 vs 回溯#

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

贪心策略的常见套路#

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

LeetCode 55 —— 跳跃游戏#

核心思路#

为什么贪心可行#

实现代码#

LeetCode 45 —— 跳跃游戏 II#

LeetCode 134 —— 加油站#

算法背后的两条关键事实#

为什么“遇负重置”有效#

实现#

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

转换思路：累加所有上涨日的涨幅#

LeetCode 435 —— 无重叠区间#

解题思路#

为什么选“最早结束”而不是“最早开始”或“最短”#

实现代码#

LeetCode 621 —— 任务调度器#

贪心下界公式#

实现#

LeetCode 763 —— 划分字母区间#

贪心思路#

实现代码#

真正应该记住的几点#

题目分类速查#

常见错误#

常见问题 Q&A#

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

贪心和 DP 该怎么选？#

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

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

加油站为什么“总油量够就一定有解”？#

贪心一定要先排序吗？#

怎么证明贪心是对的？#

贪心算法的时间复杂度一般是多少？#

LeetCode 算法模式 10 篇

读有所得？