Java算法题-解析分发糖果问题

题目

给定一个学生数组，其中每个学生都有一个分数。我们需要按照以下规则分配糖果：

• 每个学生至少分配一个糖果。
• 分数更高的学生比他的邻居获得更多的糖果。

我们需要确保最终分配的糖果数量是最少的。

引言

在这个算法问题中，我们将研究一个与公平分配糖果相关的问题。问题的核心是，给定一个学生数组，每个学生都有一个分数，我们需要按照一定规则分配糖果，确保分数更高的学生比他的邻居获得更多的糖果。

算法思路

为了最小化糖果数量，我们可以分别从左到右和从右到左遍历学生数组，保证每个学生只考虑左边和右边的邻居。

具体思路如下：

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);
    }
}

总结

分发糖果问题是一个经典的贪心算法应用场景。通过从左到右和从右到左两次遍历学生数组，我们能够确保每个学生都获得了合适数量的糖果，同时保证总糖果数量是最少的。理解贪心算法的思想对于解决类似问题非常有帮助。