LeetCode#135分发糖果

题目：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

思路

1. 想象是在爬山峰，上坡到峰顶，1、2、3...n，下坡时 n、n-1、.....1
2. 先要能理解最终的糖果数量是由上坡的次数和+下坡的次数和
3. 上坡下坡其实就是在求等差数列和，n (n+1)/2
4. 怎样定义山峰值？由于题目要求相邻孩子评分高的必须获得更多的糖果，所以山峰值应该取上坡次数和下坡次数的最大值
5. 何时结算糖果数，也就是计算山峰的上坡下坡次数和？由于到达峰顶时，不能确定峰顶的值，所以这种情况不能算作山峰形成，其他情况都算山峰形成，即可计算糖果数
6. 下坡 -> 持平，下坡 -> 上坡，上坡 -> 持平，都需要结算糖果数量
7. 所有山峰的和计算完毕后，走到最后时，需要再补算一次有峰顶的情况，并且+1，代码注释中有解释
8. 使用变量 candies 最终结果；oldSlope 记录上一次是上坡还是下坡; newSlope 记录当前是上坡还是下坡；up，down记录上坡下坡次数；

代码

class Solution {
    public int candy(int[] ratings) {
        if (ratings.length < 1) return ratings.length;
        int candies = 0;
        int oldSlope = 0;
        int up = 0;
        int down = 0;
        for (int i=1; i<ratings.length; i++) {
            int newSlope = ratings[i] > ratings[i-1] ? 1 : ratings[i] < ratings[i-1] ? -1 : 0;
            if ((oldSlope < 0 && newSlope >= 0) || (oldSlope > 0 && newSlope == 0)) {
                candies += count(up) + count(down) + Math.max(up, down); //山峰值，需要对取上坡和下坡次数中的大值，并且将山谷位置的 1 加到山峰上，让山谷作为下一个山峰的起点
                up = 0;
                down = 0;
            }
            
            if (newSlope > 0) {
                up++;
            } else if (newSlope < 0) {
                down++;
            } else {
                candies++;
            }
            
            oldSlope = newSlope;
        }
        candies += count(up) + count(down) + Math.max(up, down) + 1; //结尾是一个山峰的情况，需要补算一次数量，并且加上最后一个山谷值
        return candies;
    }
    
    private int count(int n) {
        return n * (n + 1) / 2;
    }
}