​LeetCode刷题实战135:分发糖果

共 1638字,需浏览 4分钟

 ·

2020-12-26 11:10

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做分发糖果,我们先来看题面:
https://leetcode-cn.com/problems/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?

题意


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

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

每个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?


样例


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


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


解题


https://blog.csdn.net/qq_41231926/article/details/85595981

思路:贪心算法

初始化每个人分配的糖果数量都是1。
(1)从前往后遍历ratings数组,如果发现当前位置的值比前一个位置的值要大,需要更新当前位置candies数组的值为前一个位置candies数组的值加1。
(2)从后往前遍历ratings数组,如果发现当前位置的值比后一个位置的值要大且当前位置candies数组的值小于等于后一个位置candies数组的值,那么更新当前位置candies数组的值为后一个位置candies数组的值加1。
时间复杂度和空间复杂度均是O(n),其中n为孩子的数量。

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        for (int i = 0; i < n; i++) {
            candies[i] = 1; //每人至少发一颗糖
        }
        for(int i = 1; i < n; i++){ //从前往后遍历ratings数组
            if(ratings[i] > ratings[i - 1]){
                candies[i] = candies[i - 1] + 1;
            }
        }
        for(int i = n - 2; i >= 0; i--){ //从后往前遍历ratings数组
            if(ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]){
                candies[i] = candies[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += candies[i];
        }
        return sum;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-120题汇总,希望对你有点帮助!
LeetCode刷题实战121:买卖股票的最佳时机
LeetCode刷题实战122:买卖股票的最佳时机 II
LeetCode刷题实战123:买卖股票的最佳时机 III
LeetCode刷题实战124:二叉树中的最大路径和
LeetCode刷题实战125:验证回文串
LeetCode刷题实战126:单词接龙 II
LeetCode刷题实战127:单词接龙
LeetCode刷题实战128:最长连续序列
LeetCode刷题实战129:求根到叶子节点数字之和
LeetCode刷题实战130:被围绕的区域
LeetCode刷题实战131:分割回文串
LeetCode刷题实战132:分割回文串 II
LeetCode刷题实战133:克隆图
LeetCode刷题实战134:加油站


浏览 18
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报