Leetcode 135 分发糖果

题意理解：

? ? ? ? 给出n个小孩的得分，给他们奖励糖果

? ? ? ? 奖励条件：

? ? ? ? ? ? ? ? （1）每个孩子至少分配到?1?个糖果。

????????????????（2）相邻两个孩子评分更高的孩子会获得更多的糖果。

????????

????????对于任意一个小孩，她要比左右两边的小孩分数都高，则她得到的糖要比两个小孩都多，至少多1。

? ? ? ? 对于任意一个小改，她要比左右两个小孩分数都低，则她得到的糖要比两个小孩都少，至少少1，且她最少得到一颗糖。

? ? ? ? 目标是：如何分发最少的糖，且满足分发条件。

解题思路：

? ? ? ? 采用贪心的方法来解题，则全局最优是满足分发条件的最少的糖。

? ? ? ? 每个孩子至少获得一颗糖，分少的孩子糖数尽可能的少，则再为分高的孩子发更多的糖，且需保证用糖最少。

? ? ? ? 每个孩子即需要和左边的孩子比，也需要和右边的孩子比。

? ? ? ? 为简化问题，

????????????????我们先和左边的孩子比，分比左边的大，则糖=左边孩子糖数+1

? ? ? ? ????????其次我们再和右边的孩子比，若比右边的孩子大，则糖 = Max (糖，右边孩子糖数+1)。

? ? ? ? ????????最终我们保证每个孩子得到的糖数满足分发条件且最少。
? ? ? ? ? ? ? ?

1.贪心解题

public int candy(int[] ratings) {
        int candiesSum=0;
        int[] candies=new int[ratings.length];
        //每个孩子初始化糖1
        Arrays.fill(candies,1);
        //和左边的孩子比
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                candies[i]=candies[i-1]+1;//至少左边的孩子多一个糖
            }
        }
        //和右边的孩子比
        for(int i= ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candies[i]=Math.max(candies[i+1]+1,candies[i]);//保证即满足左孩子，又比右孩子多
            }
        }
        //统计糖
        for(int i=0;i<candies.length;i++) candiesSum+=candies[i];
        return candiesSum;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(n)

n为输入数组长度。