[Leetcode] Candy 分糖果

张宪坤发布于2019-08-14 12:40 / 3013人阅读

摘要：贪心法复杂度时间空间思路典型的贪心法，如果一个孩子比另一个孩子的分高，我们只多给块糖。我们可以先从左往右遍历，确保每个孩子根他左边的孩子相比，如果分高，则糖要多个，如果分比左边低，就只给一颗。

Candy

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?

贪心法 复杂度

时间 O(N) 空间 O(N)

思路

典型的贪心法，如果一个孩子比另一个孩子的分高，我们只多给1块糖。我们可以先从左往右遍历，确保每个孩子根他左边的孩子相比，如果分高，则糖要多1个，如果分比左边低，就只给一颗。然后我们再从右往左遍历，确保每个孩子跟他右边的孩子相比，如果分高则糖至少多1个（这里至少多1个的意思是，我们要取当前孩子手里糖的数量，和其右边孩子糖的数量加1，两者的较大值）。

代码

public class Solution {
    public int candy(int[] ratings) {
        if(ratings.length <= 1){
            return ratings.length;
        }
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        // 先从左往右分糖，分数较高的多拿一颗糖，分数较少的只拿一颗糖
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i - 1]){
                candies[i] = candies[i - 1] + 1;
            } else {
                candies[i] = 1;
            }
        }
        int sum = candies[candies.length - 1];
        // 再从右往左继续分糖，分数较高的确保比右边多一颗就行了
        for(int i = ratings.length - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                candies[i] = Math.max(candies[i + 1] + 1, candies[i]);
            }
            sum += candies[i];
        }
        return sum; 
    }
}

云服务器 GPU云服务器 Candy LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[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
leetcode135. Candy

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

shmily 2019-08-15 14:26 评论0 收藏0
【LeetCode】贪心算法--分发糖果（135）

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

刘永祥 2019-07-30 18:46 评论0 收藏0
京东实习生招聘题目解析(二)

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

UnixAgain 2019-07-30 14:27 评论0 收藏0
函数范式入门(惰性求值与函数式状态)

摘要：纯函数式状态随机数生成器很明显，原有的函数不是引用透明的，这意味着它难以被测试组合并行化。售货机在输出糖果时忽略所有输入本章知识点惰性求值函数式状态第二节惰性求值与函数式状态在下面的代码中我们对List数据进行了一些处理 List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3) 考虑一下这段程序是如何求值的，如果我们跟踪一下...

Jrain 2019-08-16 13:45 评论0 收藏0