LeetCode--135

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

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

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

毫无头绪，看来是脑子不好使。

让我来瞅瞅正确答案：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int>left(n);
        for(int i=0;i<n;i++)
        {
            if(i>0&&ratings[i]>ratings[i-1])
            {
                left[i]=left[i-1]+1;
            }
            else{
                left[i]=1;
            }
        }
        int right=0,ret=0;
        for(int i=n-1;i>=0;i--)
        {
            if(i<n-1&&ratings[i]>ratings[i+1])
            right++;
            else
            right=1;
            ret+=max(left[i],right);
        }
        return ret;
        
 
    }
};

先容我细细品味，是先从左到右遍历，而后从右往左遍历。嗯嗯嗯。。。

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。

左规则：当 ratings[i−1]<ratings[i]\textit{ratings}[i - 1] < \textit{ratings}[i]ratings[i−1]<ratings[i] 时，iii 号学生的糖果数量将比 i−1i - 1i−1 号孩子的糖果数量多。

右规则：当 ratings[i]>ratings[i+1]\textit{ratings}[i] > \textit{ratings}[i + 1]ratings[i]>ratings[i+1] 时，iii 号学生的糖果数量将比 i+1i + 1i+1 号孩子的糖果数量多。

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

具体地，以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 iii，如果有 ratings[i−1]<ratings[i]\textit{ratings}[i - 1] < \textit{ratings}[i]ratings[i−1]<ratings[i] 那么 iii 号学生的糖果数量将比 i−1i - 1i−1 号孩子的糖果数量多，我们令 left[i]=left[i−1]+1\textit{left}[i] = \textit{left}[i - 1] + 1left[i]=left[i−1]+1 即可，否则我们令 left[i]=1\textit{left}[i] = 1left[i]=1。

在实际代码中，我们先计算出左规则 left\textit{left}left 数组，在计算右规则的时候只需要用单个变量记录当前位置的右规则，同时计算答案即可。

let me retry。

我的问题是理解错了题意：题目是，评分高的孩子必须获得更多的糖果，而不是获得更多糖果的孩子一定评分高。

所以我一直在考虑的第一个孩子和第二个孩子的评分相同，糖果数量也想通其实是多虑了。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int len=ratings.size();
        vector<int>left(len,1);
        vector<int>right(len,1);
        for(int i=1;i<len;i++)
        {
            if(ratings[i]>ratings[i-1])
            left[i]=left[i-1]+1;
            else
            left[i]=1;
        }
        for(int i=len-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1])
            right[i]=right[i+1]+1;
            else
            right[i]=1;
        }
        int  ret=0;
        for(int i=0;i<len;i++)
        {
            ret+=max(left[i],right[i]);
        }
        return ret;
    }
};