1. 排序 + 貪心選擇
適用場景:
-
任務調度問題:需要安排多個任務,盡量完成更多任務或最小沖突。
-
區間調度問題:選出最多互不重疊的區間。
-
區間覆蓋問題:用最少區間覆蓋某個范圍。
-
合并區間問題:合并重疊區間。
-
區間拆分、區間選擇優化等。
貪心思路:
-
先按結束時間(或起始時間)排序
-
依次選擇滿足條件的區間(如不重疊)
-
局部選擇結束最早或起點最晚,給后續留最大空間
詳細題目:
-
-
無重疊區間(最少移除使區間不重疊)
-
-
-
用最少數量的箭射爆氣球(區間覆蓋)
-
-
-
合并區間(合并所有重疊區間)
-
-
-
會議室 II(最少會議室數量)
-
-
-
插入區間(插入一個區間并合并)
-
-
-
劃分字母區間(分割字符串使字符只出現一次)
-
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. 最遠可達/跳躍類
適用場景:
-
跳躍游戲(判斷能否跳到末尾)
-
計算最少跳躍次數達到終點
-
加油站問題(能否繞圈一周)
-
投擲覆蓋范圍問題
貪心思路:
-
維護當前最遠可達位置
-
每一步更新最遠可達距離或當前位置
-
檢查能否繼續前進
詳細題目:
-
-
跳躍游戲(能否到達末尾)
-
-
-
跳躍游戲 II(最少跳躍次數)
-
-
-
加油站(找到起點)
-
-
-
會議室 II(類似區間最大重疊數,也可用貪心管理資源)
-
-
-
用最少數量的箭射爆氣球(與跳躍范圍相似)
-
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. 區間合并 / 覆蓋類
適用場景:
-
合并重疊區間
-
劃分區間或字符串
-
最小覆蓋子串(雙指針配合貪心)
貪心思路:
-
按起點排序
-
合并或擴展覆蓋區間
-
利用當前區間更新狀態
詳細題目:
-
-
合并區間
-
-
-
劃分字母區間
-
-
-
最小覆蓋子串
-
-
-
區間列表的交集
-
-
-
插入區間
-
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. 買賣股票系列
適用場景:
-
買賣股票問題求最大利潤
-
允許買賣次數有限/無限
-
買入賣出時機貪心選擇
貪心思路:
-
對于無限次買賣,累積所有上漲差價
-
對于有限次買賣,結合動態規劃和貪心
詳細題目:
-
-
買賣股票的最佳時機
-
-
-
買賣股票的最佳時機 II
-
-
-
買賣股票的最佳時機 III(結合DP)
-
-
-
買賣股票的最佳時機 IV(結合DP)
-
-
-
最佳買賣股票時機含冷凍期(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
貪心思路:
-
按面額降序,盡可能多用最大面額
-
直到滿足目標金額或無法找零
詳細題目:
-
-
零錢兌換(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. 字符串貪心類
適用場景:
-
生成字典序最小/最大字符串
-
拼接最大數
-
匹配模式(解碼字符串)
-
字符串劃分問題
貪心思路:
-
按字符優先級選擇
-
利用棧或雙指針輔助選擇
-
維護當前最優局部狀態
詳細題目:
-
-
拼接最大數
-
-
-
字符串解碼
-
-
-
去除重復字母
-
-
-
不同字符的最小子序列
-
-
-
劃分字母區間(字符串貪心和區間結合)
-