"每一步都选当前看起来最好的,最终结果就是全局最好的"——这个听起来有点天真的策略,就是贪心算法。它没有统一的代码模板,难的恰恰是"判断这题能不能贪"。这篇文章用四个经典问题带你建立这种直觉,并看清贪心什么时候会失效。

1. 贪心是什么:局部最优通向全局最优

贪心算法的信条是:每一步都做当前看起来最优的选择,并且不回头。它不像动态规划那样记录所有子问题的解,也不像回溯那样尝试所有可能,而是"一条道走到黑"。这带来两个极端:写起来又快又短;但一旦题目不适合贪心,答案就错得悄无声息。所以学贪心,第一课是学会怀疑。

先看一个直觉例子:手上有 1、5、10、25 美分的硬币,要凑出 36 美分,怎么用最少的硬币?正常人的做法是:先拿最大的 25,再拿 10,再拿 1——这就是贪心。每次尽量用大面额,正是"当前最优"。

def coin_change_greedy(amount, coins):
    coins = sorted(coins, reverse=True)   # 大面额在前
    count = 0
    for c in coins:
        if amount == 0:
            break
        count += amount // c    # 尽量多用这张面额
        amount %= c             # 剩余部分交给更小面额
    return count if amount == 0 else -1   # 凑不齐返回 -1

print(coin_change_greedy(36, [1, 5, 10, 25]))   # 3:25+10+1
print(coin_change_greedy(30, [1, 5, 10, 25]))   # 2:25+5

注意 amount // c 是整除——"这张面额最多能用几张",然后取余把剩下的交给更小面额。这个"从大到小逐个消化"的框架,是很多贪心题的雏形。

2. 反例:贪心不是万能的

现在把面额换成 [1, 3, 4],凑 6。贪心会先拿 4,剩 2,只能拿两个 1,一共 3 枚;但最优解是 3 + 3,只要 2 枚。贪心在这里失效了——因为"先用大面额"破坏了后面凑数的灵活性。这个反例要背下来,它是面试里解释"为什么这题不能用贪心"的经典素材。

# 面额 [1, 3, 4],凑 6
# 贪心:4 + 1 + 1 = 3 枚;最优:3 + 3 = 2 枚
print(coin_change_greedy(6, [1, 3, 4]))   # 3,不是最优!
# 这种"任意面额"的找零问题,正确解法是动态规划

所以看到"找零钱"先别急着贪:只有当硬币面额满足一定条件(比如现实货币那种"整除链")时贪心才正确,通用解法是动态规划。记住:贪心题往往有隐藏的"结构",比如排序后、满足某个不等式。

3. 区间调度:按结束时间排序

经典问题:给你一堆会议时间区间 [开始, 结束),一个人最多能参加多少场不重叠的会议?贪心策略是:每次选结束时间最早的会议——结束得早,给后面的会议留的空间就越大。这个策略可以证明是最优的,因为它永远在"不后悔地"给未来让路。

def interval_schedule(intervals):
    intervals.sort(key=lambda x: x[1])   # 按结束时间升序
    count = 0
    last_end = float('-inf')
    for s, e in intervals:
        if s >= last_end:      # 与上一场不冲突
            count += 1
            last_end = e
    return count

meetings = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]
print(interval_schedule(meetings))   # 3:(1,3)(3,6)(6,8)

为什么按开始时间或时长排序都不行?按开始时间排,可能选中一个超长会议把后面全挡了;按时长排,可能选中一个位置尴尬的短会议。只有"结束最早"同时保证了"开始得也足够早"。排序依据的选择,正是贪心题的核心考点。

4. 跳跃游戏:维护最远可达位置

你在数组的 0 号位置,nums[i] 表示从 i 最多能往后跳多远,问能否跳到最后一个位置。贪心思路:一路走,一路维护当前能到达的最远位置 farthest。只要最远位置能覆盖当前位置,就继续往前走;如果某一步发现最远位置够不着当前位置,说明被困住了。

def can_jump(nums):
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:          # 当前位置已经够不着
            return False
        farthest = max(farthest, i + n)
    return True

print(can_jump([2, 3, 1, 1, 4]))   # True
print(can_jump([3, 2, 1, 0, 4]))   # False,卡在 0 上

这个解法妙在不需要真的模拟每一步往哪跳,只需要维护一个上界。每个位置能跳到多远,只影响上界,不影响"我此刻站在哪"——因为我总是从能覆盖的最远位置接着探。

升级版:问最少跳几次能到终点。思路类似,但要记录"当前这一跳的边界" cur_end:在边界内走完,跳跃次数加一,同时把边界更新成这期间发现的 farthest。

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0
    jumps = 0
    cur_end = 0      # 当前这跳能到的边界
    farthest = 0     # 扫描中发现的全局最远
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:      # 走到当前跳的边界
            jumps += 1
            cur_end = farthest
    return jumps

print(jump([2, 3, 1, 1, 4]))   # 2:先到 1 号位,再到终点

对比两版代码:判断"能不能"只需要一个上界;求"最少几次"需要把上界按"跳"切段。这个递进关系在贪心题里很常见,建议两版都手写一遍。

5. 分发饼干:双排序 + 双指针

最后来个轻松但同样经典的题:每个孩子有胃口值,每块饼干有尺寸值,只有饼干尺寸不小于胃口才能喂饱一个孩子,问最多能喂饱几个。贪心策略:胃口小的孩子优先,并且给他"刚好够吃"的最小饼干——把大饼干留给胃口大的孩子。

def find_content_children(g, s):
    g.sort()      # 孩子胃口升序
    s.sort()      # 饼干尺寸升序
    i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:   # 这块饼干能喂饱当前孩子
            i += 1
        j += 1             # 不管喂没喂饱,饼干都用掉了
    return i

print(find_content_children([1, 2, 3], [1, 1]))   # 1
print(find_content_children([1, 2], [1, 2, 3]))   # 2

两个指针分别指向"下一个要喂的孩子"和"下一块要用的饼干"。饼干要么喂饱当前孩子(孩子指针前进),要么太小直接跳过(只有饼干指针前进)。两个数组各扫一遍,瓶颈在排序,复杂度 O(n log n)。

6. 贪心的适用边界:怎么判断能不能贪

贪心没有万能判定公式,但有三个实用检查:第一,最优子结构——局部最优选择之后,剩下的问题还是同类型的子问题;第二,贪心选择性质——存在一个最优解是以"当前贪心选择"开头的,选了它不会把路走死;第三,实在拿不准就先用暴力或动态规划写一版对拍,随机生成小数据验证贪心是否正确。很多竞赛选手就是靠对拍来"试"贪心的。

7. 总结与练习

这节的核心不是背代码,而是建立三种直觉:找零钱式的"按面额从大到小"、区间调度式的"按结束时间排序"、跳跃游戏式的"维护可达上界"。贪心题写起来往往不到十行,难的是证明与识别——多积累经典模型,遇到新题时往这些模型上靠。

💡 面试时说"这题用贪心"之前,先自己举一个反例试试。举不出反例,贪心才值得一试;举得出,赶紧换动态规划。

练习题: