LeetCode135. Candy

1、题目链接

https://leetcode.com/problems/candy/

2、解题思路

这道题的意思是说，有N个小孩子，老师给这N个小孩子的表现打了分，然后需要根据小孩子的得分来给他们分发糖果，当然了，分数高的小孩子得到糖果的数量一般会更多，分发糖果的要求有两个：

• 要求每个小孩子至少都能分到一颗糖果
• 要求在两个相邻的小孩之间，分数高的小孩一定比分数低的小孩分到的糖果要更多

最后问老师最少要准备多少颗糖果；我的第一想法是依次遍历每个小孩的评分，然后根据评分的高低来给至少一个糖果，首先初始第一个小孩得到一颗糖果，那么用他的评分去和他相邻的第二个小孩做比较，如果第二个小孩分数比他高，那么第二个小孩应该得到的糖果数是第一个小孩得到的糖果数+1，否则的话他只能得到1颗糖果，然后依次类推，但是到后面我们会发现，有可能排在前面小孩的分数比排在后面小孩的分数高，但是他们得到的糖都是1，所以我们需要更新一下前面小孩得到的糖果，我们能确定的是排在最后面的小孩最终得到的糖果一定是正确的，所以我们就反向遍历来更新排在前面小孩得到的糖果

3、代码

public int candy(int[] ratings) {
    if (null == ratings || ratings.length == 0) {
        return 0;
    }
    int len = ratings.length;
    if (len == 1) {
        return 1;
    }
    int[] candy = new int[len];
    candy[0] = 1;   //初始先给第1个学生一颗糖
    // 第一次遍历能保证在最后面的小孩获得的糖果数是正确的
    for (int i = 1; i < len; i++) {
        candy[i] = ratings[i] <= ratings[i - 1] ? 1 : candy[i - 1] + 1;
    }
    // 反向遍历更新靠前的小孩子最终能得到的糖果数
    for (int i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1;
        }
    }
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum += candy[i];
    }
    return sum;
}

4、结果

WX20190724-225354@2x.png