贪心算法
贪心的关键不是“每次选最大的”，而是先证明“当前这一步这样选，绝不会吃亏”，也就是局部决策不会破坏全局最优。
核心思路
贪心题最常见的切入角度就三个：
- 排序后，优先处理某种“更紧”的对象。
- 扫描时，始终维护当前最优边界。
- 构造答案时，每一步都做一个不会后悔的选择。
如果你没法说明“为什么不会后悔”，那这题大概率就不是纯贪心，而应该去想 动态规划 或搜索。
高频题型
区间类
这类题通常先排序，再维护“当前已选区间的结束位置”或“当前能覆盖到的最远位置”。
排序分配类
本质上是在问：把资源按什么顺序处理，损失最小、收益最大。
数字与字符串构造类
这类题经常和单调栈、堆、自定义排序混在一起考。
两个最有代表性的 Go 模板
模板一：区间调度
import "sort"
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
count := 1
end := intervals[0][1]
for i := 1; i < len(intervals); i++ {
if intervals[i][0] >= end {
count++
end = intervals[i][1]
}
}
return len(intervals) - count
}这里贪心的本质是：结束得越早，越给后面的区间留空间。
模板二：跳跃游戏 II
func jump(nums []int) int {
step := 0
end := 0
farthest := 0
for i := 0; i < len(nums)-1; i++ {
if i+nums[i] > farthest {
farthest = i + nums[i]
}
if i == end {
step++
end = farthest
}
}
return step
}这个模板不是在真的“跳”，而是在按层统计当前一步最远能扩到哪里，所以它和 BFS 分层思想 很像。
如何判断一道题能不能贪心
一个很实用的判断方法：先写出你直觉里的局部策略，再主动找反例。
如果下面三件事同时成立，贪心通常才比较稳：
- 局部最优决策有明确标准，比如最早结束、最远覆盖、最小代价。
- 当前选择不会影响已经做完的决策。
- 当前选择只会让后续空间更大，不会更小。
常见易错点
贪心最危险的地方不是实现，而是“你以为能贪，实际上不能贪”。
- 0/1 背包不能靠简单贪心解决。
- 多维约束题经常不是排一个字段就完事，排序规则需要严格推导。
- 区间题经常会混淆“按起点排”还是“按终点排”，这个要看你维护的量是什么。
- 股票问题里有些能贪，有些必须上状态机 DP，不能一概而论。
刷题顺序
- 先刷区间调度、区间覆盖，建立“排序 + 扫描”的感觉。
- 再刷跳跃游戏、分发饼干、分糖果，熟悉边界维护和资源分配。
- 最后再做去重字母、移掉 K 位数字、重构字符串这类构造题。
相关主题
返回：算法学习导航