题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

样例

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

算法分析

记忆化搜索

• 1、f[i]记录的是i同学至少分发多少糖果
• 2、dfs(x)表示计算好 f[x] 的值并进行返回
• 3、搜索过程中，当枚举 x 时，初始f[x] = 1，往左右两边进行递归，
  • 若左边的孩子比x孩子成绩低时，则f[x] = max(f[x], dfs(x - 1) + 1)
  • 若右边的孩子比x孩子成绩低时，则f[x] = max(f[x], dfs(x + 1) + 1)

时间复杂度 $O(n)$

Java 代码

class Solution {
    static int[] f;
    static int dfs(int x, int[] ratings)
    {
        if(f[x] != -1) return f[x];
        f[x] = 1;

        if(x - 1 >= 0 && ratings[x] > ratings[x - 1]) f[x] = Math.max(f[x], dfs(x - 1, ratings) + 1);
        if(x + 1 < ratings.length && ratings[x] > ratings[x + 1]) f[x] = Math.max(f[x], dfs(x + 1, ratings) + 1);

        return f[x];
    }
    public int candy(int[] ratings) {
        int n = ratings.length;
        f = new int[n + 10];
        Arrays.fill(f, -1);

        int res = 0;
        for(int i = 0;i < n;i ++) res += dfs(i, ratings);

        return res;
    }
}