分发糖果(贪心算法)

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

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

    每个孩子至少分配到 1 个糖果。
    相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

https://leetcode.cn/problems/candy

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

• 任意位置如果此人分数比左边的低则他分的糖果比左边的低
  

• 如果此人分数比左边的高且比右边的也高那么他分得的糖果都高
• 使用拆分数组

ratings:[1,3,3,2,1,4,2,2,5,2,1]

lefts:[1,2,1,1,1,2,1,1,2,1,1]

righs:[1,1,3,2,1,2,1,1,3,2,1]

public static int candy(int[] ratings){
//        剪枝
        if (ratings==null||ratings.length<=0){
            return 0;
        }
        int ans=0;
//        定义左数组，
        int[] lefts=new int[ratings.length];
//        index=0位置分得的糖果设置为1
        lefts[0]=1;
        int N=ratings.length;
        for (int i=1;i<N;i++){
//            如果该位置分数大于左边，则糖果数比左边+1
            if (ratings[i]>ratings[i-1]){
                lefts[i]=(lefts[i-1]+1);
            }else {
                lefts[i]=1;
            }
        }
//      定义右数组，
        int[] rights=new int[ratings.length];
//        index=N-1位置分得的糖果数设置为1
        rights[N-1]=1;
        for (int i=N-2;i>=0;i--){
//          如果该位置分数大于右边，则糖果数比右边+1
            if (ratings[i]>ratings[i+1]){
                rights[i]=(rights[i+1]+1);
            }else {
                rights[i]=1;
            }
        }
//      遍历，取出相应位置的最大值
        for (int i=0;i<N;i++){
            ans+=Math.max(lefts[i],rights[i]);
        }
        return ans;
    }