贪心算法 (Greedy Algorithms)

greedy algorithmsgreedyLeetCodealgorithminterview

贪心算法 (Greedy Algorithms)

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。

基础概念

贪心策略

基本思路:
1. 建立数学模型来描述问题
2. 把求解的问题分成若干个子问题
3. 对每个子问题求解，得到子问题的局部最优解
4. 把子问题的解局部最优解合成原来问题的一个解

适用条件

  1. 最优子结构
  2. 贪心选择性质
  3. 无后效性

经典问题

1. 跳跃游戏

LeetCode 55 - Jump Game

输入: [2,3,1,1,4]

贪心过程:
位置 0: 可以跳到 [1,2]
位置 1: 可以跳到 [2,3,4]
位置 2: 可以跳到 [3]
位置 3: 可以跳到 [4]
位置 4: 到达终点

返回: true
def canJump(nums):
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    
    return True

2. 分发糖果

LeetCode 135 - Candy

输入: [1,0,2]
评分:  1 0 2
糖果:  2 1 2

过程:
1. 每个孩子至少1个糖果
2. 从左到右扫描，右边分数更高就多给一个
3. 从右到左扫描，左边分数更高就多给一个
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)

3. 任务调度

LeetCode 621 - Task Scheduler

输入: tasks = ["A","A","A","B","B","B"], n = 2

调度过程:
A -> B -> idle -> A -> B -> idle -> A -> B

示意图:
A B _   第一轮
A B _   第二轮
A B     第三轮
def leastInterval(tasks, n):
    # 统计每个任务出现的次数
    frequencies = [0] * 26
    for t in tasks:
        frequencies[ord(t) - ord('A')] += 1
    
    # 找到出现次数最多的任务
    max_freq = max(frequencies)
    max_count = frequencies.count(max_freq)
    
    # 计算最少需要的时间单位
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

4. 买卖股票的最佳时机

LeetCode 122 - Best Time to Buy and Sell Stock II

输入: [7,1,5,3,6,4]

贪心策略:
7 1 5 3 6 4
  ↓ ↑ ↓ ↑ ↓
  买 卖 买 卖

利润: (5-1) + (6-3) = 7
def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

高级应用

1. 区间调度

会议时间:
(1,4), (4,5), (2,3), (3,6)

贪心策略:
1. 按结束时间排序
2. 选择结束最早的会议
3. 移除重叠的会议
4. 重复步骤2-3

2. 哈夫曼编码

字符频率:
A:45  B:13  C:12  D:16  E:9  F:5

构建哈夫曼树:
     100
    /    \
   45    55
  /     /  \
 A    25    30
     /  \   /  \
    13  12 16   14
    B    C  D   /  \
                9    5
                E    F

3. 最小生成树

Prim算法:
   2
A---B
|\  |\
4| \ |3
 |  \|
 C---D
   1

常见技巧

  1. 排序预处理
  2. 双向扫描
  3. 区间合并
  4. 优先队列
  5. 反向思考

相关题目