LeetCode - Candy（糖果分配）

題目描述

有 n 個小朋友排成一列，並且每個孩子有一個數組 ratings 表示他們的評分。你需要按照以下規則分配糖果：

1. 每個孩子至少分配到 1 顆糖果。
2. 評分較高的孩子要比相鄰評分較低的孩子獲得更多的糖果。

請計算最少需要多少顆糖果，才能滿足上述要求。

範例：

輸入：ratings = [1,0,2]
輸出：5
解釋：你可以給這些孩子分配 [2,1,2] 顆糖果。

輸入：ratings = [1,2,2]
輸出：4
解釋：你可以給這些孩子分配 [1,2,1] 顆糖果，第三個孩子的評分和第二個孩子相同，因此可以拿 1 顆糖果。

解法思路

要確保糖果數量最少，同時滿足分配規則，我們可以通過兩次遍歷解決這個問題。

解法：兩次遍歷

1. 從左到右遍歷：先遍歷一次列表，確保每個孩子的糖果數比左邊評分低的孩子多。
2. 從右到左遍歷：再從右往左遍歷一次，確保每個孩子的糖果數比右邊評分低的孩子多。

這樣可以保證每個孩子都會在滿足規則的情況下獲得最少的糖果數。

步驟

1. 初始化每個孩子的糖果數為 1。
2. 從左到右遍歷，若當前孩子評分比左邊的孩子高，則糖果數設置為左邊孩子糖果數 + 1。
3. 從右到左遍歷，若當前孩子評分比右邊的孩子高，則糖果數設置為右邊孩子糖果數 + 1，但要保留糖果數的最大值（避免減少糖果數）。
4. 最後將糖果數的總和作為結果返回。

範例代碼

以下是 Python 的實現：

def candy(ratings):
    n = len(ratings)
    candies = [1] * n  # 每個孩子至少有 1 顆糖果

    # 從左到右遍歷
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # 從右到左遍歷
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    # 計算最少的糖果數
    return sum(candies)

代碼解析

1. 初始化糖果數：先為每個孩子分配 1 顆糖果。
2. 從左到右遍歷：當右邊孩子評分比左邊高時，右邊孩子糖果數設為左邊糖果數 + 1。
3. 從右到左遍歷：當左邊孩子評分比右邊高時，左邊孩子糖果數設為右邊糖果數 + 1，但保留更大的糖果數。
4. 計算總糖果數：累加糖果數陣列中的元素。

時間和空間複雜度

• 時間複雜度：O(n)，其中 n 是孩子的數量，我們遍歷列表兩次。
• 空間複雜度：O(n)，用於存儲每個孩子的糖果數。