135.分发糖果

题目：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。 那么这样下来，老师至少需要准备多少颗糖果呢？   链接： https://leetcode-cn.com/problems/candy 示例 1： 输入：[1,0,2] 输出：5 解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。  

分析：

首先是先所有孩子都有一个糖果，以示例1分析，如下表所示：

评分表

1

0

2

糖果数

1

1

1

再根据要求，评分比自己旁边高的孩子必须要比旁边孩子获得更多的糖果。 我们很容易想到通过左右各遍历比较一趟来实现孩子获得更多糖果，为了求最少需要准备的糖果，我们每次只让评分更多的孩子比邻位孩子的糖果数多一个。 从左到右遍历后的糖果数表

1

1

2

再从右到左遍历 后的糖果数表

2

1

2

所以示例一的结果很容易得出是5 很容易写出代码如下：  

int candy(vector<int>& ratings) {
        int size = ratings.size();
        int num = 0;
        vector<int> temp(size,1); // 初始每一个孩子一个糖果
        for (int i = 1; i < size; ++i)
        {
            if (ratings[i] > ratings[i-1])
            {
                temp[i] = temp[i-1] + 1;
            }
        }
        for (int j = size - 1; j > 0; --j)
        {
            if (ratings[j-1] > ratings[j])
            {
                temp[j-1] = temp [j] + 1;
            }
        }
        for (int k = 0; k < ratings.size(); ++k)
        {
           num += temp[k];
        }
        return num;
    }

  但是这样会存在一个问题，就是在第二次遍历的时候是否需要进行一个糖果数的判断？ 反例：   评分表

1

3

4

5

2

按上述代码走一遍 先都分配一个，糖果数的表如下：

1

1

1

1

1

从左到右遍历后的糖果数表

1

2

3

4

1

再从右到左遍历 后的糖果数表

1

2

3

2

1

这时得出结果为9，很明显是有问题的，出问题的数就是下标第三位的数，它在遍历第二遍时，比第一次遍历时更小了，导致他比左边评分比他低的人获得的糖果数最少，这就违反了上边的分配原则。 所以我们正确的遍历应该是： 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高， 且左边孩子当前的糖果数 不大于右边孩子的糖果数 ，则左边孩子的糖果数更新为右边孩子的糖果数加 1 。

代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        int num = 0;
        vector<int> temp(size,1); // 初始每一个孩子一个糖果
        for (int i = 1; i < size; ++i)
        {
            if (ratings[i] > ratings[i-1])
            {
                temp[i] = temp[i-1] + 1;
                
            }
        }
        for (int j = size - 1; j > 0; --j)
        {
            if (ratings[j-1] > ratings[j] && temp[j-1] <= temp[j])
            {
                temp[j-1] = temp [j] + 1;
            }
        }
        for (int k = 0; k < ratings.size(); ++k)
        {
           num += temp[k];
        }
        return num;
    }
};