贪心算法

第 16 章 · 数据结构与算法

一、贪心算法概述

贪心：每步只做当前看来最优的决策，且做了就不反悔。要证明贪心正确，通常需证：贪心选择性质——存在某个最优解包含「当前贪心选的那一步」；最优子结构——做完贪心选择后，剩余子问题仍是最优子问题。并非所有问题都适合贪心：例如一般背包问题（0-1 背包）若按「性价比」贪心会出错；需要 DP 枚举。贪心正确时，实现往往简单、时间空间都优。

二、区间调度（最多不重叠区间）

给定若干区间 [start, end]，求最多能选多少个两两不重叠的区间。贪心：按结束时间 end 升序排序，然后从左到右扫描，若当前区间与「上一个已选区间」不重叠则选入。正确性：若存在最优解，可证明存在一个最优解包含「结束最早的那个与已选不重叠的区间」，即贪心选择。时间 O(n log n)。

from typing import List


def max_non_overlapping(intervals: List[List[int]]) -> int:
    """
    最多不重叠区间数。按 end 排序，维护「上一个已选区间的 end」，
    若当前 start >= last_end 则选入并更新 last_end。
    """
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    count = 1
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= last_end:
            count += 1
            last_end = intervals[i][1]
    return count

三、跳跃游戏

数组 nums[i] 表示从下标 i 最多可跳的步数。问能否从 0 到达最后一个下标。贪心：维护当前能到达的最远位置 reach，遍历时若 i > reach 则无法到达；否则用 i+nums[i] 更新 reach。若最终 reach ≥ n-1 则能到达。时间 O(n)。

from typing import List


def can_jump(nums: List[int]) -> bool:
    """reach = 当前能到达的最远下标；若 i > reach 则 False，否则 reach = max(reach, i+nums[i])。"""
    n = len(nums)
    reach = 0
    for i in range(n):
        if i > reach:
            return False
        reach = max(reach, i + nums[i])
        if reach >= n - 1:
            return True
    return reach >= n - 1

四、分发饼干

孩子胃口 g[i]，饼干尺寸 s[j]，每人最多一块。求最多能满足几个孩子。贪心：胃口和尺寸都排序，用双指针：尽量用最小能满足当前孩子的饼干（小饼干先满足小胃口），这样不会浪费大饼干。时间 O(n log n)。

from typing import List


def find_content_children(g: List[int], s: List[int]) -> int:
    """g 胃口，s 饼干尺寸；都排序后，双指针：尽量用最小能满足当前孩子的饼干。"""
    g.sort()
    s.sort()
    i, j = 0, 0
    count = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            count += 1
            i += 1
        j += 1
    return count

五、贪心与动态规划

贪心是「每步局部最优、不回溯」；DP 是「枚举状态与转移、存子问题解」。能用贪心的问题往往可以写成 DP，但贪心更省时省空间。若贪心正确性不显然，可先写 DP 再观察是否可被贪心替代，或举反例排除贪心。

六、小结

贪心每步局部最优、不回溯；需贪心选择性质与最优子结构。区间调度按 end 排序选不重叠；跳跃维护最远可达；分发饼干排序后双指针。下一章为总结与进阶。

七、例题

以下例题使用 Python 3 类型标注与注释。

from typing import List


def find_min_arrow_shots(points: List[List[int]]) -> int:
    """按右端点排序，每箭射在某一区间的右端，能覆盖所有与之重叠的区间；再找下一组。"""
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows = 1
    last_end = points[0][1]
    for i in range(1, len(points)):
        if points[i][0] > last_end:
            arrows += 1
            last_end = points[i][1]
    return arrows

from typing import List


def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    """按 start 排序，若当前与 result 最后一个重叠则合并，否则 append。"""
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    result: List[List[int]] = [intervals[0][:]]
    for i in range(1, len(intervals)):
        start, end = intervals[i][0], intervals[i][1]
        last = result[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            result.append([start, end])
    return result

from typing import List


def jump(nums: List[int]) -> int:
    """步数 step，当前步能到的右界 border，下一步能到的最远 next_reach。"""
    if len(nums) <= 1:
        return 0
    step = 0
    border = 0
    next_reach = 0
    for i in range(len(nums)):
        if i > border:
            step += 1
            border = next_reach
        next_reach = max(next_reach, i + nums[i])
    return step

from typing import List


def lemonade_change(bills: List[int]) -> bool:
    """维护 5 元张数 five 和 10 元张数 ten。20 时优先找 10+5，否则 5+5+5。"""
    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:
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False
    return True