贪心算法套路模板＋详细适用场景＋经典题目清单

1. 排序 + 贪心选择

适用场景：

• 任务调度问题：需要安排多个任务，尽量完成更多任务或最小冲突。

• 区间调度问题：选出最多互不重叠的区间。

• 区间覆盖问题：用最少区间覆盖某个范围。

• 合并区间问题：合并重叠区间。

• 区间拆分、区间选择优化等。

贪心思路：

• 先按结束时间（或起始时间）排序

• 依次选择满足条件的区间（如不重叠）

• 局部选择结束最早或起点最晚，给后续留最大空间

详细题目：

• 1. 无重叠区间（最少移除使区间不重叠）

• 1. 用最少数量的箭射爆气球（区间覆盖）

• 1. 合并区间（合并所有重叠区间）

• 1. 会议室 II（最少会议室数量）

• 1. 插入区间（插入一个区间并合并）

• 1. 划分字母区间（分割字符串使字符只出现一次）

func GreedyIntervalScheduling(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }

    // 1. 按区间结束时间排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    count := 1             // 至少选一个区间
    end := intervals[0][1] // 当前选择区间的结束时间

    // 2. 遍历所有区间，选择开始时间 >= 当前end的区间
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end {
            count++
            end = intervals[i][1]
        }
    }
    return count
}

2. 最远可达/跳跃类

适用场景：

• 跳跃游戏（判断能否跳到末尾）

• 计算最少跳跃次数达到终点

• 加油站问题（能否绕圈一周）

• 投掷覆盖范围问题

贪心思路：

• 维护当前最远可达位置

• 每一步更新最远可达距离或当前位置

• 检查能否继续前进

详细题目：

• 1. 跳跃游戏（能否到达末尾）

• 1. 跳跃游戏 II（最少跳跃次数）

• 1. 加油站（找到起点）

• 1. 会议室 II（类似区间最大重叠数，也可用贪心管理资源）

• 1. 用最少数量的箭射爆气球（与跳跃范围相似）

func CanJump(nums []int) bool {
    maxReach := 0
    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            // 当前位置不可达
            return false
        }
        maxReach = max(maxReach, i+nums[i])
    }
    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3. 区间合并 / 覆盖类

适用场景：

• 合并重叠区间

• 划分区间或字符串

• 最小覆盖子串（双指针配合贪心）

贪心思路：

• 按起点排序

• 合并或扩展覆盖区间

• 利用当前区间更新状态

详细题目：

• 1. 合并区间

• 1. 划分字母区间

• 1. 最小覆盖子串

• 1. 区间列表的交集

• 1. 插入区间

func MergeIntervals(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{intervals[0]}
    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        if intervals[i][0] <= last[1] {
            // 重叠，合并区间
            if intervals[i][1] > last[1] {
                last[1] = intervals[i][1]
            }
        } else {
            // 无重叠，加入
            merged = append(merged, intervals[i])
        }
    }
    return merged
}

4. 买卖股票系列

适用场景：

• 买卖股票问题求最大利润

• 允许买卖次数有限/无限

• 买入卖出时机贪心选择

贪心思路：

• 对于无限次买卖，累积所有上涨差价

• 对于有限次买卖，结合动态规划和贪心

详细题目：

• 1. 买卖股票的最佳时机

• 1. 买卖股票的最佳时机 II

• 1. 买卖股票的最佳时机 III（结合DP）

• 1. 买卖股票的最佳时机 IV（结合DP）

• 1. 最佳买卖股票时机含冷冻期（DP）

func MaxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}

5. 零钱兑换贪心（适用特定硬币集）

适用场景：

• 面额有贪心最优结构，如常见硬币（1、5、10、25）

• 求最少硬币数

• 注意非标准面额需DP

贪心思路：

• 按面额降序，尽可能多用最大面额

• 直到满足目标金额或无法找零

详细题目：

• 1. 零钱兑换（DP推荐，贪心不一定适用）

• 零钱兑换问题变形：只用特定面额找零问题

func CoinChangeGreedy(coins []int, amount int) int {
    // 降序排列面额
    sort.Slice(coins, func(i, j int) bool {
        return coins[i] > coins[j]
    })

    count := 0
    for _, coin := range coins {
        if amount == 0 {
            break
        }
        count += amount / coin
        amount %= coin
    }
    if amount != 0 {
        return -1
    }
    return count
}

6. 字符串贪心类

适用场景：

• 生成字典序最小/最大字符串

• 拼接最大数

• 匹配模式（解码字符串）

• 字符串划分问题

贪心思路：

• 按字符优先级选择

• 利用栈或双指针辅助选择

• 维护当前最优局部状态

详细题目：

• 1. 拼接最大数

• 1. 字符串解码

• 1. 去除重复字母

• 1. 不同字符的最小子序列

• 1. 划分字母区间（字符串贪心和区间结合）