当前位置：首页 > web >正文

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

web 2025/8/12 10:02:16

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
}