首页 > itarticle > [leetcode]candy

[leetcode]candy

admin 11月 12, 2020 0

题目描述

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?

代码

public class  {
    
    //最后从后往前遍历扫描，如果第i-1个小孩的等级比i高但糖的数目却小于或等于，那么i-1的糖数目等于i糖数目+1
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0) return 0;

        int[] nums = new int[ratings.length];

        Arrays.fill(nums, 1);

        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                nums[i] = nums[i-1] + 1;
            }
        }
        //此时在这个循环也可以统计糖的总和，但是为了可读性还是再开一个循环吧
        for(int i = ratings.length - 1; i > 0; i--){
            if(ratings[i-1] > ratings[i] && nums[i-1] <= nums[i]) nums[i-1] = nums[i] + 1;
            //if(ratings[i-1] > ratings[i]) nums[i-1] = Math.max(nums[i] + 1, nums[i-1]);
        }

        int res = 0;
        for(int i = 0; i < nums.length; i++){
            res += nums[i];
        }

        return res;
    }
}