1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    int candy(vector<int>& ratings)
    {
        int n = ratings.size();
        std::vector<int> candy(n, 1);  // 初始化每个孩子分 1 个糖果

        int res = 0;
        for (int i = 0; i < n; ++i)
            res += minCandy(ratings, candy, i);  // 递归更新糖果数

        return res;  // 返回总糖果数
    }

    // 递归函数：计算第 child 个孩子最少需要的糖果数
    int minCandy(std::vector<int>& ratings, std::vector<int>& candy, int child)
    {
        if (candy[child] != 1)  // 如果已计算过，直接返回
            return candy[child];

        // 左边孩子评分更低，当前孩子糖果+1
        if (child > 0 && ratings[child - 1] < ratings[child])
            candy[child] = std::max(candy[child], minCandy(ratings, candy, child - 1) + 1);

        // 右边孩子评分更低，当前孩子糖果+1
        if (child + 1 < ratings.size() && ratings[child] > ratings[child + 1])
            candy[child] = std::max(candy[child], minCandy(ratings, candy, child + 1) + 1);

        return candy[child];  // 返回计算结果
    }
};