题解 | 分糖果问题

1、解题思路

这是一个典型的贪心算法问题，可以通过两次遍历数组来解决：

1. 从左到右遍历 ：确保每个孩子与其左侧相邻孩子满足糖果分配规则。 如果当前孩子的得分比左侧高，则当前孩子的糖果数至少为左侧孩子的糖果数加1。否则，当前孩子的糖果数至少为1（初始值）。
2. 从右到左遍历 ：确保每个孩子与其右侧相邻孩子满足糖果分配规则。 如果当前孩子的得分比右侧高，则当前孩子的糖果数至少为右侧孩子的糖果数加1（但不要减少当前已分配的糖果数）。否则，保持当前糖果数不变。
3. 求和：将两次遍历后的糖果数取最大值，然后求和。

这种方法确保每个孩子既满足左侧规则又满足右侧规则，同时使用最少糖果。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n = arr.size();
        if (n == 0) {
            return 0;
        }

        vector<int> candies(n, 1);  // 每个孩子至少 1 个糖果

        // 从左到右遍历, 确保比左边高时糖果更多
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历, 确保比右边高时糖果更多
        for (int i = n - 2; i >= 0; --i) {
            if (arr[i] > arr[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }

        // 计算糖果总数
        int total = 0;
        for (int num : candies) {
            total += num;
        }

        return total;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int n = arr.length;
        if (n == 0) return 0;

        int[] candies = new int[n];
        Arrays.fill(candies, 1); // 每个孩子至少1个糖果

        // 从左到右遍历，确保比左边高时糖果更多
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历，确保比右边高时糖果更多
        for (int i = n - 2; i >= 0; --i) {
            if (arr[i] > arr[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 计算总糖果数
        int total = 0;
        for (int num : candies) {
            total += num;
        }

        return total;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# pick candy
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        if n == 0:
            return 0
        
        candies = [1] * n  # 每个孩子至少1个糖果
        
        # 从左到右遍历，确保比左边高时糖果更多
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                candies[i] = candies[i - 1] + 1
        
        # 从右到左遍历，确保比右边高时糖果更多
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        
        return sum(candies)

3、复杂度分析

1. 初始分配：每个孩子至少1个糖果。
2. 从左到右遍历：确保每个孩子比左侧高分时糖果数更多。
3. 从右到左遍历：确保每个孩子比右侧高分时糖果数更多，同时不破坏之前的分配。
4. 时间复杂度：两次遍历，O(n)。
5. 空间复杂度：使用额外数组存储糖果数，O(n)。