贪心算法 (Greedy)

LeetCodeGreedy贪心算法算法

贪心算法（Greedy）

贪心算法每一步都选择当前最优解，期望通过局部最优达到全局最优。适用于满足贪心选择性质和最优子结构的问题。

原理与特点

  • 每一步都做出当前最优选择，不回溯、不枚举所有可能
  • 适合区间调度、资源分配、最小生成树等问题
  • 有时不能保证全局最优，但实现简单、效率高

常见应用

  • 区间调度
  • 跳跃游戏
  • 零钱兑换（部分情况）
  • 分发糖果
  • 买卖股票的最佳时机
  • Huffman编码、最小生成树（Kruskal）

典型例题

1. 跳跃游戏

def canJump(nums):
    farthest = 0
    for i, x in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + x)
    return True

2. 分发糖果

def candy(ratings):
    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)

优缺点

  • 优点：实现简单，效率高
  • 缺点：不一定得到全局最优解

相关文章