LeetCode 135.Candy （分发糖果）

我不是女神ヾ 2022-05-08 10:06 193阅读 0赞

题目描述：

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

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

*  每个孩子至少分配到 1 个糖果。
 *  相邻的孩子中，评分高的孩子必须获得更多的糖果。

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

**示例 1:**

输入: [1,0,2]
    输出: 5
    解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

**示例 2:**

输入: [1,2,2]
    输出: 4
    解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
         第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

AC C++ Solution:

通过两次遍历，一次遍历比较前一个元素，一次遍历比较后一个元素。

class Solution {
    public:
        int candy(vector<int>& ratings) {
            int size = ratings.size();
            if(size <= 1)
                return size;
            
            vector<int> num(size,1);
            for(int i = 1; i < size; i++) {     //正序比较
                if(ratings[i] > ratings[i-1])
                    num[i] = num[i-1] + 1;
            }
            
            for(int i = size-1; i > 0; i--) {   //逆序比较
                if(ratings[i-1] > ratings[i])
                    num[i-1] = max(num[i]+1,num[i-1]);
            }
            
            int result = 0;
            for(auto i : num)
                result += i;
            
            return result;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 135. 分发糖果

135. 分发糖果题干描述解题思路总结代码实现题干描述 [力扣入口][Link 1] 老师想给孩子们分发糖果，有 N 个孩子站

待我称王封你为后i/ 2023年10月16日 15:23/ 0 赞/ 23 阅读

相关 LeetCode_数组_困难_135.分发糖果

目录 1.题目 2.思路 3.代码实现（Java） 1.题目 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需

叁歲伎倆/ 2023年10月10日 18:36/ 0 赞/ 22 阅读

相关 135.分发糖果 Candy

题目描述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：1.每个孩子至少

忘是亡心i/ 2022年12月30日 08:04/ 0 赞/ 186 阅读

相关 leetcode 135. Candy | 135. 分发糖果（原创图文详解，Java）

题目 [https://leetcode.com/problems/candy/][https_leetcode.com_problems_candy] ![在这里插

小咪咪/ 2022年10月10日 12:47/ 0 赞/ 230 阅读

相关 135. 分发糖果

> 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 > > 你需要按照以下要求，帮助老师给这些孩子分发糖果： > > 每个

叁歲伎倆/ 2022年10月05日 10:59/ 0 赞/ 159 阅读

相关 Leetcode 135. 分发糖果

题目重述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子

一时失言乱红尘/ 2022年09月13日 15:26/ 0 赞/ 167 阅读

相关 leetcode 135 分发糖果

前言题目：[135. 分发糖果][135.] 参考题解：[分发糖果-力扣官方题解][-] -------------------- 提交代码我没想出来，看

桃扇骨/ 2022年08月28日 09:55/ 0 赞/ 169 阅读

相关 leetcode 135. Candy

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

迈不过友情╰/ 2022年07月28日 09:51/ 0 赞/ 187 阅读

相关 [Leetcode][python]Candy/分发糖果

题目大意一直线上站了N个孩子，每个孩子都有一个属于自己的数字，现在按照如下规则给孩子分发糖果：每个孩子至少有一个糖果；相邻的孩子中数字比较大的那个拿的糖果也比较多。求最

左手的ㄟ右手/ 2022年06月05日 05:05/ 0 赞/ 217 阅读

相关 LeetCode 135.Candy （分发糖果）

题目描述：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个

我不是女神ヾ/ 2022年05月08日 10:06/ 0 赞/ 194 阅读