贪心必刷9题：从区间问题到序列贪心

引言

贪心算法「每一步取局部最优，最终得到全局最优」，是面试中出现频率极高、但正确性最容易想当然的一类题。做贪心题，答案不只是「选哪个」，更是「为什么这个局部选择是对的」——这也是面试官最常追问的点。

本文精选 9 道高频贪心题，按「区间问题 → 序列贪心 → 计数与分配」分类，每题给出 Python 实现、贪心选择的直觉，以及正确性证明的核心思路。

前置：/leetcode-dynamic-programming-essential-problems/（贪心与 DP 的区别）、https://plumephp.com/greedy/（贪心原理与证明方法）。

目录

• 1. 贪心 vs 动态规划：什么时候能用贪心
• 2. 分发饼干（LeetCode 455）
• 3. 跳跃游戏 II（LeetCode 45）
• 4. 无重叠区间（LeetCode 435）
• 5. 用最少数量的箭引爆气球（LeetCode 452）
• 6. 柠檬水找零（LeetCode 860）
• 7. 加油站（LeetCode 134）
• 8. 买卖股票的最佳时机 II（LeetCode 122）
• 9. 单调递增的数字（LeetCode 738）
• 10. 贪心题解速查表
• 延伸阅读

1. 贪心 vs 动态规划：什么时候能用贪心

贪心选择性质：一个问题存在贪心解，意味着「局部最优解」本身就是「全局最优解」的一部分。证明常用交换论证（Exchange Argument）：假设全局最优解中的某个选择和贪心选择不同，证明把贪心选择换进去不劣化结果。

面试提示：先分析能否证明贪心正确；证不出来，立即转向 DP——DP 是兜底方案。

2. 分发饼干（LeetCode 455）

问题：每个孩子有一个胃口 g[i]，每块饼干有一个尺寸 s[j]，饼干 j 只能给胃口 ≤ s[j] 的孩子。问最多能满足几个孩子。

贪心直觉：把胃口和饼干都升序排序。用尽量小的饼干去满足尽量小胃口的孩子——小饼干留给胃口大的孩子只会浪费。

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

证明思路（交换论证）：若全局最优里有个孩子 A（胃口较小）用大饼干 p 满足，而饼干 q（较小）给了孩子 B（胃口较大）。因为 q ≥ g[A]（贪心选择可行）且 p ≥ g[B] ≥ g[A]，交换后 A 用 q、B 用 p 依然都能满足，解不劣化。故贪心不劣于任意最优解。

3. 跳跃游戏 II（LeetCode 45）

问题：数组 nums[i] 表示从 i 最多能跳多远，求从位置 0 跳到末尾的最小步数。

贪心直觉：BFS 层序遍历的贪心版。当前层能覆盖的区间是 [curEnd, maxReach]，每跳一步就把区间扩展到下一个最大可达点，保证步数最少。

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0
    max_reach = 0      # 全局最远可达
    cur_end = 0        # 当前这一跳的边界
    steps = 0
    for i in range(n - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == cur_end:          # 走到这一跳边界，必须再跳一步
            steps += 1
            cur_end = max_reach
    return steps

证明思路：每次在可达区间内选择「能延伸到最远的点」作为下一跳起点，得到的区间覆盖 [0, n-1] 的层数最少。等价于 BFS 求最短路径，BFS 天然给出最少层数。

对比：单纯「每次跳最远」的反例 —— [3, 1, 1, 1] 第一跳跳 3 需要 1 步，但如果直接算最远可达区间 [0,3]，仍只需 1 步。跳跃游戏 II 的核心是区间扩展而非「单点最远」。

4. 无重叠区间（LeetCode 435）

问题：给定若干区间，求移除最少多少个区间，使剩余区间互不重叠。

贪心直觉：按右端点升序排序，优先保留右端点最小的区间。因为右端点越小，留给后面区间的空间越大。

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])    # 按右端点排序
    keep = 0
    end = float('-inf')
    for s, e in intervals:
        if s >= end:          # 不重叠，保留
            keep += 1
            end = e
    return len(intervals) - keep

为什么按右端点排序而不是左端点：

证明思路（交换论证）：贪心保留的第一个区间是右端点最小的区间 R。若全局最优解不含 R，设其第一个区间是 R’，则 R 的右端点 ≤ R’ 的右端点，把 R’ 替换为 R 不劣化后续选择。归纳可得贪心最优。

5. 用最少数量的箭引爆气球（LeetCode 452）

问题：气球用区间 [xs, xe] 表示，一支箭在 x 处竖直射出可引爆所有覆盖 x 的气球，求引爆全部气球的最少箭数。

贪心直觉：这是「最多不重叠区间」的变体——一支箭能覆盖的气球必然是「相互重叠的区间」。按右端点排序，一箭射在某个气球区间的右端点，可引爆所有与该点重叠的气球。

def find_min_arrow_shots(points):
    points.sort(key=lambda x: x[1])
    arrows = 0
    end = float('-inf')
    for s, e in points:
        if s > end:            # 与当前箭的覆盖点不重叠，需要新箭
            arrows += 1
            end = e
    return arrows

与「无重叠区间」的关系：无重叠区间是「保留最多」，本问题是「覆盖全部最少箭」——两者对偶。最小箭数 = 最多不重叠区间的区间数（若允许端点重叠，则按 s > end 判重叠）。

6. 柠檬水找零（LeetCode 860）

问题：顾客排队付 5/10/20 美元，你初始无零钱，判断能否给每位顾客正确找零。

贪心直觉：找零 20 时优先用 10+5 组合，因为 5 美元更通用（能找 10 也能找 20），要尽量留住 5。

def lemonade_change(bills):
    five = ten = 0
    for b in bills:
        if b == 5:
            five += 1
        elif b == 10:
            if five == 0:
                return False
            five -= 1
            ten += 1
        else:                      # 20 美元
            if ten and five:       # 优先 10+5
                ten -= 1
                five -= 1
            elif five >= 3:        # 再考虑 5+5+5
                five -= 3
            else:
                return False
    return True

证明思路：10 美元只能用于找 20，而 5 美元既能找 10 又能找 20。10 是「更稀缺」的找零资源，优先消耗 10 绝不会让后续找零变难——所以「有 10 优先给 10」是安全的。

7. 加油站（LeetCode 134）

问题：环形加油站，gas[i] 表示到 i 站能加的油，cost[i] 表示从 i 开到 i+1 的耗油，油箱无上限但初始为空。求能绕一圈的起始站，或返回 -1。

贪心直觉：

1. 若总油量 ≥ 总耗油（sum(gas) >= sum(cost)），一定存在可行起点。
2. 从任意起点扫描，一旦当前累计油量 < 0，说明该区间任何点都不能作为起点，起点直接跳到失败点的下一站。

def can_complete_circuit(gas, cost):
    n = len(gas)
    total = cur = 0
    start = 0
    for i in range(n):
        total += gas[i] - cost[i]   # 全程净油量
        cur += gas[i] - cost[i]     # 当前累计净油量
        if cur < 0:
            start = i + 1           # 起点后移，重置累计
            cur = 0
    return start if total >= 0 else -1

为什么失败点之前都不能做起点：从 s 出发到 i 处油量 < 0，意味着 sum(gas[s..i]) < sum(cost[s..i])。对任意 s ≤ k ≤ i，若以 k 为起点到 i 仍会油量不足（因为从 s 到 k 的净油量为正或你跳过的那段也是净油量为负的前缀，起点后移只会在 i 处更早耗尽）。所以可以直接跳过整段。

8. 买卖股票的最佳时机 II（LeetCode 122）

问题：可以多次买卖（同一天可先卖再买），求最大利润。

贪心直觉：只要今天比昨天贵，就赚这笔差价——把每个上升段都吃掉，等价于「每次都抓住正收益的相邻差价」。

def max_profit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

证明思路：任意一次「持有一段 [a, b]」的收益 = prices[b] - prices[a] = 段内相邻差之和。由于可在任意天买卖，只要把所有正相邻差都加进来，总收益就等于「买在每段谷底、卖在每段峰顶」的全局最优——任何跨越负差区的持有都只会减少收益。

对比：股票 I（121）只能买卖一次 → 用「维护最低价」的单次扫描；股票 II 可无限次 → 吃所有正差价；含冷冻期（309）→ 状态机 DP。见 /leetcode-dynamic-programming-essential-problems/。

9. 单调递增的数字（LeetCode 738）

问题：给定整数 n，返回 ≤ n 的最大数字，且各位从左到右单调递增（非严格）。

贪心直觉：从右往左找第一个破坏递增的位置，把它减 1，后面全部变成 9。

def monotone_increasing_digits(n):
    s = list(str(n))
    i = 0
    # 从左到右找第一个递减点
    while i < len(s) - 1 and s[i] <= s[i + 1]:
        i += 1
    if i == len(s) - 1:          # 本身已单调递增
        return n
    # 从右往左把减 1 后仍破坏递增的位置处理掉
    while i > 0 and s[i - 1] > s[i] - 1:
        s[i - 1] = str(int(s[i - 1]) - 1)
        i -= 1
    # 把 i 之后全部置 9
    for j in range(i + 1, len(s)):
        s[j] = '9'
    return int(''.join(s))

示例：n = 332 → 递减点在 index 1（3 > 2）→ 3 减 1 仍 > 2-1？s[0]=3 > s[1]-1=2 → s[0]→2，i=0 → 后置 [0] 为 2, [1] 和 [2] 为 9 → 299（单调递增，且最大）。

10. 贪心题解速查表

记忆口诀：区间问题按右端点排序；序列问题找「累积变负就重置」；分配问题按排序后贪心匹配。

延伸阅读

• /leetcode-dynamic-programming-essential-problems/ — 贪心 vs DP 的对比
• /leetcode-backtracking-problems/ — 与回溯互补的搜索类题目
• https://plumephp.com/greedy/ — 贪心原理：交换论证、归纳法与经典问题
• LeetCode 贪心标签 — 完整题库