題目

給定一個學生數組，其中每個學生都有一個分數。我們需要按照以下規則分配糖果：

• 每個學生至少分配一個糖果。
• 分數更高的學生比他的鄰居獲得更多的糖果。

我們需要確保最終分配的糖果數量是最少的。

引言

在這個算法問題中，我們將研究一個與公平分配糖果相關的問題。問題的核心是，給定一個學生數組，每個學生都有一個分數，我們需要按照一定規則分配糖果，確保分數更高的學生比他的鄰居獲得更多的糖果。

算法思路

為了最小化糖果數量，我們可以分別從左到右和從右到左遍歷學生數組，保證每個學生隻考慮左邊和右邊的鄰居。

具體思路如下：

1. 初始化一個糖果數組 candies，並將所有元素初始化為 1，表示每個學生至少分配一個糖果。
2. 從左到右遍歷學生數組，如果當前學生的分數比左邊的學生高，那麼他的糖果數應比左邊的學生多一個。
3. 從右到左遍歷學生數組，如果當前學生的分數比右邊的學生高，那麼他的糖果數應比右邊的學生多一個。
4. 最終，糖果數組 candies 中的元素和即為所需的最小糖果數量。

代碼實現

以下是使用 Java 實現的解決方案：

public class Candy {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        // 從左到右遍歷，確保右邊比左邊高的學生糖果數更多
        for (int i = 1; i < n; i  ) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1]   1;
            }
        }
        // 從右到左遍歷，確保左邊比右邊高的學生糖果數更多
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i   1]) {
                candies[i] = Math.max(candies[i], candies[i   1]   1);
            }
        }
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies  = candy;
        }
        return totalCandies;
    }
}

算法分析

• 時間復雜度：遍歷學生數組兩次，時間復雜度為 O(N)，其中 N 是學生的數量。
• 空間復雜度：使用了一個額外的糖果數組，空間復雜度為 O(N)，其中 N 是學生的數量。

示例和測試

我們可以使用以下代碼進行測試：

public class Main {
    public static void main(String[] args) {
        Candy solution = new Candy();
        int[] ratings = {1, 0, 2};
        int minCandies = solution.candy(ratings);
        System.out.println("最小糖果數量: "   minCandies);
    }
}

總結

分發糖果問題是一個經典的貪心算法應用場景。通過從左到右和從右到左兩次遍歷學生數組，我們能夠確保每個學生都獲得了合適數量的糖果，同時保證總糖果數量是最少的。
理解貪心算法的思想對於解決類似問題非常有幫助。