leetcode135. Candy

shmily 发布于2019-08-15 14:26 / 2909人阅读

摘要：题目要求假设有个孩子站成一排，每个孩子拥有一个评估值。我们可以观察到，每次最远只需要额外分发到距离当前最近的评分最高的那个孩子。因为他的糖果数量的增加并不会影响到之前孩子。当有多个最近评分最高的孩子时，则选择最后一个。

题目要求

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

假设有N个孩子站成一排，每个孩子拥有一个评估值。现在要根据以下的需求给孩子们分发糖果：

每个孩子至少有一颗糖

有更高评估值的孩子应当比两侧孩子得到的糖更多

问最少要发出多少颗糖？

思路和代码

这里我们可以举一个例子来先试着分配一下：
假设有10个孩子，每个孩子对应的评估分别是[3,4,5,7,2,3,3,2,1,10]
按照尽量少分配的原则，前四个孩子我们会分别给1，2，3，4颗糖，从第五个孩子开始，我们只需要给1颗糖就可以满足需求。

前五个孩子的分配情况如下：
[1,2,3,4,1, , , , , ]

第六个孩子和第七个孩子评估值相同，我们还是可以将第七个孩子赋值1，因为这样还是可以满足要求。结果如下：
[1,2,3,4,1,2,1, , , ]

到第八个孩子的时候，我们发现这个孩子评估值比第七个孩子低，但是基于每个孩子最少一颗糖的原理，我们必须给第八个孩子一颗糖并且开始回调前面分发的糖的数量。
[1,2,3,4,1,2,2,1, , ]

第九个孩子的情况一样，我们同样给他一颗糖并调整：
[1,2,3,4,1,2,3,2,1, ]

最后孩子评分比前一个评分高，我们只需直接在前一个孩子的数量上加1即可：
[1,2,3,4,1,2,3,2,1,2]

由此我们可以总结出以下几个结论：

当后一个孩子比前一个孩子评分高时，直接在前一个孩子糖果数量基础上加1

当后一个孩子比前一个孩子评分低时

前一个孩子糖果数量大于1，则该孩子糖果数量为1

前一个孩子糖果数量为1，则该孩子糖果数量为1，并且将前面相应孩子的糖果数量加1

当后一个孩子和前一个孩子评分一样多，则该孩子糖果数量为1

这是我们只需要知道，当后一个孩子比前一个孩子评分低，且前一个孩子糖果数量为1时，最少由多少个孩子需要额外分发一个糖果。我们可以观察到，每次最远只需要额外分发到距离当前最近的评分最高的那个孩子。因为他的糖果数量的增加并不会影响到之前孩子。
至于该评分最高的孩子是否需要增加糖果，则要看后面的孩子增加后的糖果数量是不是比他高。

当有多个最近评分最高的孩子时，则选择最后一个。

代码如下：

    public int candy(int[] ratings) {
        int count = 1;
        int summitIndex = 0;
        int summitCandy = 1;
        int prevCandy = 1;
        for(int i = 1 ; i ratings[i-1]){
                prevCandy++;
                count += prevCandy;
                summitIndex = i;
                summitCandy = prevCandy;
            }else if(ratings[i] < ratings[i-1]){
                if(prevCandy == 1){
                    count += (i - summitIndex) + (i-summitIndex >= summitCandy ? 1 : 0);
                }else{
                    prevCandy = 1;
                    count += prevCandy;
                }
            }else{
                prevCandy = 1;
                count += prevCandy;
                summitIndex = i;
                summitCandy = prevCandy;
            }
        }
        return count;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

海外云主机私有云 Candy 135邮箱 135cdn Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68610.html

【LeetCode】贪心算法--分发糖果（135）

摘要：今日题目老师想给孩子们分发糖果，有个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。相邻的孩子中，评分高的孩子必须获得更多的糖果。示例输入输出解释你可以分别给这三个孩子分发颗糖果。第三个孩子只得到颗糖果，这已满足上述两个条件。今日题目老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖...

刘永祥 2019-07-30 18:46 评论0 收藏0
[Leetcode] Candy 分糖果

摘要：贪心法复杂度时间空间思路典型的贪心法，如果一个孩子比另一个孩子的分高，我们只多给块糖。我们可以先从左往右遍历，确保每个孩子根他左边的孩子相比，如果分高，则糖要多个，如果分比左边低，就只给一颗。 Candy There are N children standing in a line. Each child is assigned a rating value. You are gi...

张宪坤 2019-08-14 12:40 评论0 收藏0
[LintCode/LeetCode] Candy

摘要：保证高的小朋友拿到的糖果更多，我们建立一个分糖果数组。首先，分析边界条件如果没有小朋友，或者只有一个小朋友，分别对应没有糖果，和有一个糖果。排排坐，吃果果。先往右，再往左。右边高，多一个。总和加上小朋友总数，就是要准备糖果的总数啦。 Problem There are N children standing in a line. Each child is assigned a rat...

baishancloud 2019-08-14 15:43 评论0 收藏0
[LeetCode] 575. Distribute Candies

Problem Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribu...

djfml 2019-08-16 13:47 评论0 收藏0
京东实习生招聘题目解析(二)

摘要：买糖果题目来源京东实习生招聘原题链接可在线提交赛码网问题描述某糖果公司专门生产儿童糖果，它最受儿童欢迎的糖果有两个序列，均采用盒式包装。小东希望你能帮她解决这一问题。最近比较忙，又有一段时间没写题目了，终于在前几天把赛码网上，JD的2016秋招和2017实习生招聘剩下的4星难度题目做了，至此所有4星难度题目都解决了，5星难度题目还剩下一个应该是计算几何学的题目，因为这块我不熟悉，后面...

UnixAgain 2019-07-30 14:27 评论0 收藏0