贪心算法——分发糖果

老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师们会根据每个孩子的表现，预先给他们评分。
需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到一个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

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

题目分析：

对于这个问题，主要的条件是要相邻的孩子，得分高的拿的糖果要多（不包括相等得分），还有就是每个人最少都要有一个。
解决这个问题采用贪心算法，

• 首先初始化每个人分配的糖果数量都是1，然后这个算法需要遍历两遍；
• 第一遍从左往右遍历，如果当前孩子的分数大于前一个孩子的分数，则当前孩子的得到的糖果在前一个孩子的基础上加1；
• 第二遍从右往左遍历，如果当前孩子的分数大于他右边孩子的分数，且他的糖果不比他右边孩子的糖果多，则糖果数在他右边孩子的基础上加一；
• 最后将所有孩子的糖果数相加即可。

class Solutions {
    func candy(_ ratings: [Int]) -> Int {
        var candys: [Int] = []
        for _ in 0..<ratings.count {
            candys.append(1)
        }
        for i in 0..<ratings.count - 1 {
            if ratings[i+1] > ratings[i] {
                candys[i+1] = candys[i] + 1
            }
        }
        for i in (1 ..< ratings.count).reversed(){
            if ratings[i-1] > ratings[i] {
                candys[i-1] = max(candys[i] + 1, candys[i-1])
            }
        }
        let num = candys.reduce(0, +)
        print(candys)
        return num
    }
}