【贪心算法】之 分糖果（中等题）

- n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
- 你需要按照以下要求，给这些孩子分发糖果：
		每个孩子至少分配到 1 个糖果。
		相邻两个孩子评分更高的孩子会获得更多的糖果。
		请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

这道题目一定是要确定一边之后，再确定另一边，先比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼

解题思路：

1. 初始化两个数组left、right；每个小孩至少都有一个candy，所以初始化数组值为1；
2. 分两个规则，从左边遍历数组，num[ i+1] >num[i]，则num[i+1]的糖果比num[i]多一个，记录在left中；
3. 同理，右至左遍历学生成绩并记录在 right 中，可以保证所有学生糖数量 满足右规则 。
4. 最后我们贪心，取以上 2 轮遍历 left 和 right 对应学生糖果数的 最大值 ，这样则 同时满足左规则和右规则 ，即得到每个同学的最少糖果数量。

import java.util.Arrays;
//分糖果
public class leetcode_135 {
    public static void main(String[] args) {
        int[] ratings = {1, 3, 2, 2, 1};
        System.out.println(candy(ratings));
    }
    public static int candy(int[] ratings) {
        int index = 0;
        //初始化两个数组
        int[] left=new int[ratings.length];
        int[] right=new int[ratings.length];
        //初始值都为1；
        Arrays.fill(left,1);
        Arrays.fill(right,1);
        //左规则
        for (int i = 0; i < ratings.length-1; i++) {
            if (ratings[i+1]>ratings[i]){
                left[i+1]=left[i]+1;
            }
        }
        //右规则
        for (int i = ratings.length-1; i>0; i--) {
            if (ratings[i-1]>ratings[i]){
                right[i-1]=right[i]+1;
            }
        }
        //找最大 求和即可
        int sum=0;
        for (int i = 0; i <ratings.length ; i++) {
            sum+=Math.max(left[i],right[i]);
        }
        return sum;
    }
}