题目

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

思路

dp[i]：记录i的获取糖果树

1. 从左向右扫描，保证一个方向上分数更大的糖果更多
2. 从右向左扫描，保证另一个方向上分数更大的糖果更多

代码

public class Candy {
    public static int candy(int[] ratings) {
        int[] dp = new int[ratings.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        

        for (int i = 1; i < dp.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        

        for (int i = dp.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && dp[i] <= dp[i + 1]) {
                dp[i] = dp[i + 1] + 1;
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length ; i++) {
            res += dp[i];
        }

        return res;
    }

/*    public static void main(String[] args) {
        candy(new int[]{2,2});
    }*/
}