---

🍬 標題一：貪心核心思想——發糖果時的最優分配策略

貪心算法 (Greedy Algorithm) 是一種簡單直觀的算法策略。它在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望得到一個全局最優解。這就像你作為班主任發糖果，每次都想讓眼前的孩子滿意，希望這種局部最優能帶來整體最優的效果。

三大適用條件

并非所有問題都適合用貪心算法解決，它通常需要滿足以下三個條件：

1. 貪心選擇性質 (Greedy Choice Property)：每一步的局部最優選擇，都能導致最終的全局最優解。例如，在“硬幣找零”問題中，如果硬幣面額系統是“標準”的（如 1, 5, 10, 25 美分），那么每次都優先選擇最大面額的硬幣就能得到最少硬幣數。
2. 無后效性 (Optimal Substructure)：當前的選擇不會影響后續子問題的最優解，即后續問題的最優解不依賴于之前的選擇，只依賴于當前狀態。例如，在“區間調度”中，一旦你選擇了最早結束的會議，后續會議的選擇空間并不會因此受限，而是基于剩余時間繼續做決策。
3. 子問題可合并 (Overlapping Subproblems)：雖然這是動態規劃的特征之一，但在貪心算法中，這意味著局部解能夠直接或以簡單的方式構成全局解。例如，在霍夫曼編碼中，每次合并兩個最小頻率的節點，最終能構建出最優的二叉樹。

與 DP 的關鍵區別

貪心算法和動態規劃都涉及將問題分解為子問題，但它們在解決方式上存在根本差異：

• 貪心：做選擇時不考慮未來，只看當前局部最優，并且一旦做出選擇就不可回退。它不需要存儲所有子問題的解。
• 動態規劃：會探索所有可能的局部最優解，并存儲它們，通過狀態轉移方程來構建全局最優解。它具有“回退”機制，可以從之前的多種選擇中推導出當前的最優。

# 貪心 vs 動態規劃：以「硬幣找零」為例
# 假設硬幣面額為 [1, 5, 10, 25]，找零 30
# 貪心：25 + 5 (2枚)
# DP：10 + 10 + 10 (3枚) 或 25 + 1 + 1 + 1 + 1 + 1 (6枚)# 貪心（可能無法得到最優解，例如面額 [1, 15, 25], 找零 30, 貪心會是 25+1+1+1+1+1 (6枚), 最優是 15+15 (2枚)）
def coinChangeGreedy(coins, amount):coins.sort(reverse=True) # 優先使用大面額硬幣count = 0for coin in coins:while amount >= coin:amount -= coincount += 1return count if amount == 0 else -1 # 如果 amount 不為 0，說明無法找零# DP（保證最優解）
def coinChangeDP(coins, amount):# dp[i] 表示湊齊金額 i 所需的最少硬幣數dp = [float('inf')] * (amount + 1)dp[0] = 0 # 湊齊金額 0 需要 0 枚硬幣for i in range(1, amount + 1): # 遍歷所有可能的金額for coin in coins:         # 遍歷所有硬幣面額if i >= coin:# 如果當前金額 i 大于等于當前硬幣面額 coin# 那么湊齊 i 的最少硬幣數可能是：# 1. 不使用當前硬幣，沿用 dp[i] (之前可能計算過)# 2. 使用當前硬幣，那么剩下的金額 i - coin 需要 dp[i - coin] 枚硬幣dp[i] = min(dp[i], dp[i - coin] + 1)return dp[amount] if dp[amount] != float('inf') else -1 # 如果為 inf，表示無法湊齊# print(coinChangeGreedy([1, 15, 25], 30)) # 輸出 6
# print(coinChangeDP([1, 15, 25], 30))     # 輸出 2

---

? 標題二：區間調度問題——會議室的高效安排

區間調度問題是一個經典的貪心算法應用場景。

經典問題

給定若干會議的開始和結束時間 [start, end]，如何安排最多的不重疊會議，使得一個會議室可以安排盡可能多的會議？

貪心策略

按結束時間排序：優先選擇最早結束的會議。為什么？因為最早結束的會議會給后續會議留出最大的時間空隙，從而使得我們有機會安排更多的會議。

import java.util.Arrays;
import java.util.Comparator; // 引入 Comparator 接口class Solution {public int maxEvents(int[][] intervals) {// Step 1: 按結束時間升序排序會議// 如果結束時間相同，則按開始時間升序排序（可選，但通常不影響結果）Arrays.sort(intervals, (a, b) -> a[1] - b[1]);int count = 0; // 記錄安排的會議數量int lastEndTime = Integer.MIN_VALUE; // 記錄上一個已安排會議的結束時間// Step 2: 遍歷排序后的會議for (int[] meeting : intervals) {int currentStart = meeting[0];int currentEnd = meeting[1];// 如果當前會議的開始時間 >= 上一個已安排會議的結束時間// 說明當前會議可以安排，且不與之前的會議重疊if (currentStart >= lastEndTime) {count++;            // 安排該會議lastEndTime = currentEnd; // 更新上一個會議的結束時間}}return count;}
}

變形題

• 需要多間會議室時：這通常會轉化為其他問題，例如“最小箭射氣球”（LeetCode 452），它尋找最少數量的“箭頭”能射爆所有氣球（代表區間），本質上是尋找最少數量的區間來覆蓋所有給定區間。
• 帶權值的區間：如果每個會議有不同的“價值”或“收益”，需要最大化總收益，那么純粹的貪心可能不再適用，通常需要結合動態規劃來解決（例如“最大收益的兼職工作”）。

---

🏃 標題三：跳躍游戲——從起點到終點的最少步數

跳躍游戲系列問題也是貪心算法的經典應用。

兩類經典問題

1. 能否到達終點（LeetCode 55）：給定一個非負整數數組 nums，每個元素 nums[i] 代表你在位置 i 最多可以向前跳躍的長度。判斷你是否能從第一個位置跳到最后一個位置。

   def canJump(nums):max_reach = 0 # 記錄當前能到達的最遠位置# 遍歷數組，直到到達終點或無法繼續前進for i in range(len(nums)):if i > max_reach: # 如果當前位置 i 已經超出了之前能到達的最遠位置return False  # 說明無法到達終點# 更新能到達的最遠位置：當前位置 i + 從當前位置能跳的距離 nums[i]max_reach = max(max_reach, i + nums[i])if max_reach >= len(nums) - 1: # 如果能到達或越過終點return True                # 則成功到達return True # 如果循環結束（即已經遍歷完數組），說明可以到達終點
   

2. 最少跳躍次數（LeetCode 45）：給定一個非負整數數組 nums，同上，求到達最后一個位置的最少跳躍次數。

   def jump(nums):if len(nums) <= 1:return 0jumps = 0          # 跳躍次數current_end = 0    # 當前跳躍能到達的最遠邊界farthest = 0       # 在當前跳躍范圍內，下一步能到達的最遠位置for i in range(len(nums) - 1): # 遍歷到倒數第二個位置，因為最后一個位置不需要再跳# 更新在當前跳躍范圍內能到達的最遠位置farthest = max(farthest, i + nums[i])if i == current_end: # 如果當前位置 i 達到了當前跳躍的邊界jumps += 1       # 進行一次跳躍current_end = farthest # 更新下一次跳躍的邊界為當前能到達的最遠位置# 注意：這里不需要檢查 farthest 是否能到達終點，# 因為 for 循環條件保證了最終 current_end 會達到或超過 len(nums) - 1return jumps
   

關鍵洞察

貪心地在每一步選擇能跳最遠的選項（但不是盲目地跳到最遠，而是規劃好下一次跳躍的邊界）。

---

🛒 標題四：高頻面試題——分發糖果（雙向貪心）

問題

在一個班級里，有 n 個孩子，他們的能力值用整數數組 ratings 表示。你需要給這些孩子分發糖果，并滿足以下兩個條件：

1. 每個孩子至少分到 1 顆糖果。
2. 能力值比其相鄰孩子高的孩子，必須分到比相鄰孩子更多的糖果。

求最少需要分發多少顆糖果。

雙向遍歷策略

這個問題不能簡單地從左到右或從右到左遍歷一次，因為它有雙向的依賴關系。需要進行雙向貪心：

1. 從左到右遍歷：確保右邊的孩子比左邊高的，能獲得更多糖果。
2. 從右到左遍歷：確保左邊的孩子比右邊高的，能獲得更多糖果。
3. 取兩者最大值：最終每個孩子分到的糖果數，是兩次遍歷結果的最大值。

def candy(ratings):n = len(ratings)# left 數組：從左到右遍歷，保證 ratings[i] > ratings[i-1] 時，left[i] > left[i-1]left = [1] * n # 初始化每個孩子至少1顆糖for i in range(1, n):if ratings[i] > ratings[i - 1]:left[i] = left[i - 1] + 1# right 變量：從右到左遍歷，保證 ratings[i] > ratings[i+1] 時，當前孩子獲得更多糖# total：總糖果數，先加上 left 數組的最后一個元素right = 1total = left[n - 1] # 最后一個孩子的糖果數，至少是 left[n-1]for i in range(n - 2, -1, -1): # 從倒數第二個孩子開始，向左遍歷if ratings[i] > ratings[i + 1]:right += 1 # 如果當前孩子比右邊高，right 增加else:right = 1  # 否則，重置 right 為 1 (因為右邊孩子可能比自己高或相等)# 當前孩子實際獲得的糖果數，是 left[i] 和 right 兩者中的最大值# 這樣才能同時滿足左右兩個方向的條件total += max(left[i], right)return total

• 時間復雜度：$O(n)$，因為進行了兩次線性遍歷。
• 空間復雜度：$O(n)$，因為使用了 left 數組。可以進一步優化到 $O(1)$ 空間，但代碼會更復雜。

---

📊 總結表：貪心算法適用場景

問題類型	典型例題	貪心策略
區間問題	無重疊區間（LeetCode 435）	按結束時間排序，優先選擇最早結束的。
分配問題	分發糖果（LeetCode 135）	雙向遍歷（從左到右，從右到左）滿足約束。
跳躍問題	跳躍游戲 II（LeetCode 45）	維護當前能到達的最遠位置，并在必要時進行跳躍。
字符串構造	重構字符串（LeetCode 767）	優先使用剩余最多的字符，避免連續。
硬幣/貨幣	硬幣找零（標準面額系統）	優先使用最大面額的硬幣。

---