LeetCode Candy 分發糖果：雙遍歷貪心 O(n) 完美解法

題目描述

N 個孩子站成一排，每個有評分 ratings[i]。分糖果規則：

1. 每個孩子至少 1 顆
2. 相鄰孩子中，評分高的必須比評分低的糖果多

求最少總糖果數。

核心洞察：局部最優 → 全局最優

• 遞增段：理想分配 1, 2, 3... (左→右遍歷處理)
• 遞減段：理想分配 ..., 3, 2, 1 (右→左遍歷處理)
• 峰值點：同時屬於遞增段尾與遞減段頭，取兩遍歷結果的 最大值

雙遍歷算法

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1] * n
        
        # 左→右：處理遞增關係
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
        
        # 右→左：處理遞減關係，取最大值保證峰值滿足雙側
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candy[i] = max(candy[i], candy[i+1] + 1)
        
        return sum(candy)

執行示例

ratings = [1, 2, 3, 7, 4, 3, 2, 1]

左→右: [1, 2, 3, 4, 1, 1, 1, 1]
右→左: [1, 1, 1, 4, 3, 2, 1, 1]  (從右向左更新)
合併:  [1, 2, 3, 4, 3, 2, 1, 1]  sum = 17

複雜度

• 時間：O(n) — 兩次線性掃描
• 空間：O(n) — 糖果數組，可優化至 O(1) (單遍歷法較複雜)

為什麼取 max？

峰值點 (如 7) 左側要求 ≥ 4，右側要求 ≥ 4，取 max(4,4)=4 同時滿足兩側。若取 min 會違反某側約束。

擴展：單遍歷 O(1) 空間思路

維護 up, down, peak 計數器，遇到平/升/降切換時結算當前山谷/山峰糖果數。代碼較長，面試推薦雙遍歷版：清晰、不易錯、同樣 O(n)。