30 秒速览

  • 什么时候用：每步选择具有最优子结构，局部最优能推出全局最优
  • 核心思想：每步选当前最优，不回头
  • 与 DP 的区别：贪心不回头，DP 会考虑所有可能
  • 时间复杂度：通常 O(n) 或 O(n log n)

一、直觉建立

分糖果

有一堆糖果，你要分给尽可能多的小朋友，每个小朋友只能拿一颗糖，每种糖果数量有限。

贪心策略：优先分数量少的糖果，这样能分给更多小朋友。

贪心的本质：每一步都做当前最优选择，不回头，期望最终也是最优。

贪心 vs 动态规划

特性贪心动态规划
选择当前最优考虑所有可能
回头不回头会回退
证明需要证明自然成立
效率更高更低

贪心能用的前提：局部最优能推导全局最优（需要证明）。

二、典型例题

例题 1：LC 55. 跳跃游戏

题目：给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例：

输入：nums = [2,3,1,1,4]
输出：true（先跳 1 步到 1，再跳 3 步到最后）

贪心思路

维护能到达的最远位置。

def canJump(nums: list[int]) -> bool:
    max_reach = 0

    for i, num in enumerate(nums):
        if i > max_reach:  # 当前位置不可达
            return False

        max_reach = max(max_reach, i + num)

        if max_reach >= len(nums) - 1:
            return True

    return True

复杂度：时间 O(n)，空间 O(1)

例题 2：LC 45. 跳跃游戏 II

题目：返回到达最后一个下标的最小跳跃次数。

贪心思路

在当前能到达的范围内，选择能跳得最远的位置。

def jump(nums: list[int]) -> int:
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    current_end = 0  # 当前跳跃能到的边界
    farthest = 0     # 下一跳能到的最远位置

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:  # 到达边界，必须跳跃
            jumps += 1
            current_end = farthest

    return jumps

复杂度：时间 O(n)，空间 O(1)

例题 3：LC 435. 无重叠区间

题目：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

示例：

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1（移除 [1,3]）

贪心思路

按结束时间排序，优先保留结束早的区间。

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0

    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < end:  # 重叠
            count += 1
        else:
            end = intervals[i][1]

    return count

为什么按结束时间排序？

结束早的区间给后面留更多空间，能放下更多不重叠的区间。

复杂度：时间 O(n log n)，空间 O(1)

例题 4：LC 452. 用最少数量的箭引爆气球

题目：气球在一个水平数轴上，一支箭可以引爆所有重叠的气球，求最少需要多少支箭。

贪心思路

与无重叠区间类似，但边界相接也算重叠。

def findMinArrowShots(points: list[list[int]]) -> int:
    if not points:
        return 0

    # 按结束位置排序
    points.sort(key=lambda x: x[1])

    arrows = 1
    end = points[0][1]

    for i in range(1, len(points)):
        if points[i][0] > end:  # 不重叠
            arrows += 1
            end = points[i][1]

    return arrows

复杂度：时间 O(n log n)，空间 O(1)

例题 5：LC 763. 划分字母区间

题目：给你一个字符串 s，把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

示例：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]（"ababcbaca", "defegde", "hijhklij"）

贪心思路

  1. 先统计每个字符最后出现的位置
  2. 遍历时扩展当前区间的结束位置
  3. 到达结束位置时，划分一个片段
def partitionLabels(s: str) -> list[int]:
    # 统计每个字符最后出现的位置
    last_pos = {}
    for i, c in enumerate(s):
        last_pos[c] = i

    result = []
    start = 0
    end = 0

    for i, c in enumerate(s):
        end = max(end, last_pos[c])  # 扩展区间

        if i == end:  # 到达区间结束
            result.append(end - start + 1)
            start = i + 1

    return result

复杂度：时间 O(n)，空间 O(1)（只有 26 个字母）

例题 6：LC 406. 根据身高重建队列

题目： people[i] = [hi, ki] 表示第 i 个人的身高为 hi，前面正好有 ki 个身高大于或等于 hi 的人。重新排队。

示例：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

贪心思路

  1. 按身高降序、k 升序排序
  2. 逐个插入到 k 位置
def reconstructQueue(people: list[list[int]]) -> list[list[int]]:
    # 身高降序，k 升序
    people.sort(key=lambda x: (-x[0], x[1]))

    result = []
    for p in people:
        result.insert(p[1], p)  # 插入到 k 位置

    return result

为什么这样排序？

  • 高的人先排好，低的人插入不会影响高的人的 k 值
  • 同身高时 k 小的先插入

复杂度：时间 O(n²)，空间 O(n)

例题 7：LC 121. 买卖股票的最佳时机

题目：给定一个数组 prices，它的第 i 个元素是一支股票第 i 天的价格。如果你最多只允许完成一笔交易，计算你能获取的最大利润。

贪心思路

记录最低价格，计算每天卖出的利润。

def maxProfit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

复杂度：时间 O(n)，空间 O(1)

例题 8：LC 122. 买卖股票的最佳时机 II

题目：可以完成多笔交易，求最大利润。

贪心思路

只要明天比今天贵，今天就买明天卖。

def maxProfit(prices: list[int]) -> int:
    profit = 0

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

    return profit

为什么这样是对的？

连续涨的日子里，累计利润 = 最后一天 - 第一天，等于每天买卖的利润之和。

复杂度：时间 O(n)，空间 O(1)

例题 9：LC 134. 加油站

题目：环形路线上的加油站，求能否绕一圈，如果能，返回起始站点。

贪心思路

  1. 如果总油量 < 总消耗，不可能
  2. 从起点开始，如果中途油不够，就从下一个站点重新开始
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]

        if tank < 0:
            start = i + 1
            tank = 0

    return start

为什么这样是对的？

如果从 A 出发到 B 油不够，那么从 A 到 B 之间的任何点出发都不可能到达 B。所以直接从 B+1 开始尝试。

复杂度：时间 O(n)，空间 O(1)

例题 10：LC 135. 分发糖果

题目：n 个孩子站成一排，评分更高的孩子必须比相邻孩子得到更多糖果，每个孩子至少一颗，求最少糖果数。

贪心思路

两次遍历：

  1. 从左到右：如果右边评分高，右边糖果 = 左边 + 1
  2. 从右到左：如果左边评分高，左边糖果 = max(当前, 右边 + 1)
def candy(ratings: list[int]) -> int:
    n = len(ratings)
    candies = [1] * n

    # 从左到右
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # 从右到左
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    return sum(candies)

复杂度：时间 O(n)，空间 O(n)

三、贪心问题的判断

什么时候可以用贪心？

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 贪心选择性质：局部最优能推导全局最优
  3. 无后效性：当前选择不影响后续选择

如何证明贪心正确？

  1. 交换论证：证明任何非贪心解都可以通过交换变成贪心解，且不更差
  2. 数学归纳：证明每一步贪心选择都正确
  3. 反例排除：尝试找反例，找不到则可能是对的

四、常见错误与陷阱

错误 1：想当然用贪心

不是所有最优化问题都能贪心。比如 01 背包问题就不能。

错误 2：排序标准错误

# 无重叠区间
# 错误：按开始时间排序
intervals.sort(key=lambda x: x[0])

# 正确：按结束时间排序
intervals.sort(key=lambda x: x[1])

错误 3：边界条件

# 区间问题中，[1,2] 和 [2,3] 是否算重叠？
# 取决于题目定义，要仔细看题

五、复盘清单

触发信号

  • 最优化问题（最值、最少、最多）
  • 区间问题
  • 调度问题
  • 分配问题

判断标准

  • 是否有最优子结构？
  • 局部最优能否推导全局最优？
  • 能否举出反例？

排序策略

  • 按开始时间还是结束时间？
  • 升序还是降序？
  • 需要多个排序标准吗？

六、题目清单

基础题

题号题目难度考点
55跳跃游戏Medium最远可达
45跳跃游戏 IIMedium最少跳跃
121买卖股票Easy记录最低
122买卖股票 IIMedium累计利润
53最大子数组和Medium最大前缀和

进阶题

题号题目难度考点
435无重叠区间Medium区间调度
452引爆气球Medium区间调度
763划分字母区间Medium区间扩展
406重建队列Medium插入排序
134加油站Medium累计差值
135分发糖果Hard双向遍历