LeetCode 135.分发糖果

LeetCode 135.分发糖果题目地址:

​​https://leetcode-cn.com/problems/candy/​​

题目描述:

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

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

    1. 每个孩子至少分配到 1 个糖果。

    2. 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

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

示例 1：

输入：[1,0,2]

输出：5

解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：[1,2,2]

输出：4

解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。

          第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

题目分析:

输入为一个数组，数组存放每个孩子的评分，分数比两侧邻位孩子高的，分发的糖果应该比两侧邻位的孩子更多。每个孩子至少分配一个糖果，所以我们可以先给每个孩子获得的糖果数赋值为1，然后从左到右遍历一次，右边孩子评分比左边孩子评分高的，右边孩子糖果数更新为左边孩子糖果数加一。最后再从右到左遍历一次，左边孩子评分比右边孩子评分高的，且左边孩子当前的糖果数不大于右边孩子的糖果数，左边孩子糖果数更新为右边孩子糖果数加一。

题解:

执行用时: 2 ms

内存消耗: 39.5 MB

class Solution {
    public int candy(int[] ratings) {
        // 获取孩子的个数
        int size = ratings.length;
        // 如果孩子个数为0，即没有孩子，不用分发糖果，糖果总数为0
        // 如果孩子个数为1，即只有一个孩子，只需满足此孩子，糖果总数为1
        if (size < 2)
        {
            return size;
        }
        // 建立一个新数组存放每个孩子所获糖果数，数组长度与孩子个数相等
        int[] num = new int[size];
        // 第一步，给每个孩子分发一颗糖果
        for (int i = 0; i < size; ++i)
        {
            num[i]++;
        }
        // 第二步，从左到右遍历孩子所得评分数组
        for (int i = 1; i < size; ++i)
        {
            // 如果右边孩子评分高于左边孩子评分
            if (ratings[i - 1] < ratings[i])
            {
                // 右边孩子所得糖果数比左边孩子所得糖果数多一
                num[i] = num[i - 1] + 1;
            }
        }
        // 第三步，从右到左遍历孩子所得评分数组
        for (int i = size - 1; i > 0; --i)
        {
            // 如果左边孩子评分高于右边孩子评分
            if (ratings[i] < ratings[i - 1])
            {
                // 左边孩子所得糖果数取当前所得糖果数与右边孩子所得糖果数加一的最大值
                num[i - 1] = Math.max(num[i - 1], num[i] + 1);
            }
        }
        // 第四步，求需准备糖果的总数
        // 定义变量存放需准备糖果的总数
        int sum = 0;
        // 遍历每个孩子所得糖果数组，获得糖果总数
        for (int x : num)
        {
            sum += x;
        }
        // 返回需准备糖果的总数
        return sum;
    }
}

题目来源:力扣(LeetCode)