贪心算法（Greedy Algorithm）系统分类与经典题型详解

贪心算法（Greedy Algorithm） 是一种在每一步选择中都采取当前状态下最优决策的算法思想，常用于解决最优化问题。其核心在于：局部最优解能否推导出全局最优解。

本文从基础概念到经典题型进行系统分类与解析，涵盖从入门到进阶的所有常见问题。

---

一、贪心算法的三大核心要素

1. ✅ 贪心选择性质：每一步的局部最优选择能导致全局最优解
2. 🔁 无后效性：当前的选择不会影响后续子问题的结构
3. ⚡ 高效性：时间复杂度通常为 $O(n)$ 或 $O(n \log n)$，优于动态规划

---

二、贪心算法经典题型分类

1. 区间调度问题

（1）不相交区间选择

📅 435. 无重叠区间

• 策略：按结束时间升序排序，优先选择结束早的区间
• 代码实现：

python
def eraseOverlapIntervals(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])
    count = 1
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    return len(intervals) - count

（2）合并区间

🧩 56. 合并区间

• 策略：按起始时间排序，合并重叠区间
• 代码实现：

python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

---

2. 分配问题

（1）饼干分配

🍪 455. 分发饼干

• 策略：将最小的饼干分配给最小需求的孩子（双指针贪心）
• 代码实现：

python
def findContentChildren(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

（2）任务调度

📋 621. 任务调度器

• 策略：优先安排出现次数最多的任务，用空闲时间填充其他任务

---

3. 跳跃游戏问题

（1）能否到达终点

🏃‍♂️ 55. 跳跃游戏

• 策略：维护当前能到达的最远距离，逐步扩展
• 代码实现：

python
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）最少跳跃次数

🐾 45. 跳跃游戏 II

• 策略：在每一步选择能跳到最远范围的位置
• 代码实现：

python
def jump(nums):
    steps = 0
    cur_end = 0
    max_reach = 0
    for i in range(len(nums) - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == cur_end:
            steps += 1
            cur_end = max_reach
    return steps

---

4. 买卖股票问题

（1）无限次交易

💰 122. 买卖股票的最佳时机 II

• 策略：所有上升区间的利润累加
• 代码实现：

python
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

（2）含手续费

💰🧮 714. 最佳时机含手续费

• 策略：在价格上涨时卖出，但需扣除手续费

---

5. 字符串问题

（1）分割字符串

🔤 763. 划分字母区间

• 策略：记录每个字母的最后出现位置，按区间分割
• 代码实现：

python
def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    start = end = 0
    res = []
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            res.append(end - start + 1)
            start = end + 1
    return res

（2）移除重复字母

🧹 316. 去除重复字母

• 策略：维护单调栈，保证字典序最小且每个字母至少出现一次

---

三、贪心算法解题技巧总结

1. 📊 排序预处理：多数贪心问题需要先排序（如按起始时间、结束时间、数值大小等）
2. 🧠 反证法验证：通过假设“非贪心选择更优”来推导矛盾，证明贪心策略的正确性
3. 👆 双指针技巧：常用于区间或分配问题（如饼干分配、跳跃游戏）
4. 🔍 观察数据规律：例如股票问题中“所有上升区间和=总利润”

---

四、高频贪心算法题目列表

类型	经典题目
区间问题	435. 无重叠区间、56. 合并区间
分配问题	455. 分发饼干、621. 任务调度器
跳跃游戏	55. 跳跃游戏、45. 跳跃游戏 II
买卖股票	122. 买卖股票 II、714. 含手续费
字符串问题	763. 划分字母区间、316. 去除重复字母

---

五、总结

贪心算法的核心在于通过局部最优选择构造全局最优解。

掌握要点：

1. ✅ 严格证明贪心策略的正确性（如区间问题结束时间排序的合理性）
2. 🧱 掌握经典问题的模板（如跳跃游戏的双指针、股票问题的利润累加）
3. 🔀 区分贪心与动态规划：贪心不可回溯，动态规划需要状态转移

---

📌 推荐练习顺序：区间问题 → 分配问题 → 跳跃游戏 → 买卖股票 → 字符串问题