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

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 := 0for 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 := 0for 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 := 0for _, coin := range coins {if amount == 0 {break}count += amount / coinamount %= coin}if amount != 0 {return -1}return count
}

---

6. 字符串贪心类

适用场景：

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

• 拼接最大数

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

• 字符串划分问题

贪心思路：

• 按字符优先级选择

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

• 维护当前最优局部状态

详细题目：

• 1. 拼接最大数

• 1. 字符串解码

• 1. 去除重复字母

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

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