LeetCode 135：分糖果

問題本質與核心挑戰

給定孩子的評分數組，需滿足 “每個孩子至少1顆糖果，相鄰評分高的孩子糖果更多”，求最少糖果總數。核心挑戰：

• 相鄰約束是雙向的（左→右和右→左都需滿足），直接枚舉無法高效解決；
• 需通過 兩次貪心遍歷（左→右、右→左）分別處理單向約束，再合并結果。

核心思路：雙向貪心 + 合并約束

1. 單向約束處理（左→右遍歷）

• 定義數組 left，left[i] 表示 從左到右遍歷 時，第 i 個孩子應得的最少糖果（僅滿足“左邊約束”：若 ratings[i] > ratings[i-1]，則 left[i] = left[i-1]+1；否則為 1）。

2. 單向約束處理（右→左遍歷）

• 定義數組 right，right[i] 表示 從右到左遍歷 時，第 i 個孩子應得的最少糖果（僅滿足“右邊約束”：若 ratings[i] > ratings[i+1]，則 right[i] = right[i+1]+1；否則為 1）。

3. 合并雙向約束

• 每個孩子最終的糖果數為 max(left[i], right[i])（同時滿足左右約束），求和即為答案。

算法步驟詳解（以示例 ratings = [1,0,2] 為例）

步驟 1：左→右遍歷，處理左邊約束

孩子索引 i	評分 ratings[i]	與左邊比較（ratings[i] > ratings[i-1]）	left[i] 計算	left 數組
0	1	-（無左邊孩子）	初始為 1	[1]
1	0	0 > 1？否	設為 1	[1,1]
2	2	2 > 0？是	left[1]+1 = 2	[1,1,2]

步驟 2：右→左遍歷，處理右邊約束

孩子索引 i	評分 ratings[i]	與右邊比較（ratings[i] > ratings[i+1]）	right[i] 計算	right 數組
2	2	-（無右邊孩子）	初始為 1	[1]
1	0	0 > 2？否	設為 1	[1,1]
0	1	1 > 0？是	right[1]+1 = 2	[2,1,1]

步驟 3：合并約束，計算總和

孩子索引 i	left[i]	right[i]	max(left[i], right[i])	貢獻糖果數
0	1	2	2	2
1	1	1	1	1
2	2	1	2	2
總和	-	-	-	2+1+2=5

完整代碼（Java）

class Solution {public int candy(int[] ratings) {int n = ratings.length;if (n == 0) return 0; // 邊界處理（題目保證n≥1，可省略）// 1. 左→右遍歷，處理左邊約束int[] left = new int[n];left[0] = 1; // 第一個孩子至少1顆for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i-1]) {left[i] = left[i-1] + 1;} else {left[i] = 1;}}// 2. 右→左遍歷，處理右邊約束int[] right = new int[n];right[n-1] = 1; // 最后一個孩子至少1顆for (int i = n-2; i >= 0; i--) {if (ratings[i] > ratings[i+1]) {right[i] = right[i+1] + 1;} else {right[i] = 1;}}// 3. 合并雙向約束，計算總和int total = 0;for (int i = 0; i < n; i++) {total += Math.max(left[i], right[i]);}return total;}
}

關鍵邏輯解析

1. 左→右遍歷：確保 “右邊孩子評分更高時，糖果數比左邊多”，但無法處理“左邊孩子評分更高，右邊需更多”的情況（如 [5,4,3,2,1]，左遍歷后所有 left[i]=1，需右遍歷修正）。
2. 右→左遍歷：確保 “左邊孩子評分更高時，糖果數比右邊多”，與左遍歷互補。
3. 合并約束：取兩者最大值，保證同時滿足左右雙向約束，且糖果數最少（貪心思想：僅在必要時增加糖果）。

復雜度分析

• 時間復雜度：O(n)（兩次遍歷數組，每次 O(n)，合并遍歷 O(n)）。
• 空間復雜度：O(n)（存儲 left 和 right 數組，可優化為 O(1)，但代碼可讀性降低）。

該方法通過 兩次貪心遍歷拆分雙向約束，將復雜的雙向問題轉化為兩個單向問題，再合并求解，確保了效率和可讀性的平衡，是處理此類“雙向約束”問題的經典思路。