leetcode 135 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?

Example 1:

1
2
3

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

用一个数组保存每一个小孩的candies数目，并初始化为1。
从前往后遍历rantings，如果当前比之前一个大，candies[i] = candies[i-1]+1
从后往前遍历rantings，如果当前比他前面的一个小，candies[i-1] = max(candies[i-1], candies[i]+1)

class  {
    public int candy(int[] ratings) {
        if (ratings.length == 0) return 0;
        int n = 0;
        int[] candies = new int[ratings.length];
        for(int i=0; i<ratings.length; i++) {
            candies[i] = 1;
        }
        for (int i=1; i<ratings.length; i++) {
            if(ratings[i] > ratings[i-1]) {
                candies[i] = candies[i-1]+1;
            }
        }
        for (int i=ratings.length-1; i>0; i--) {
            if(ratings[i-1] > ratings[i]){
                candies[i-1] = Math.max(candies[i-1], candies[i]+1);
            }
        }
        
        for (int i: candies){
            n+= i;
        }
        return n;
    }
}

leetcode 135 candy

近期文章

近期评论

标签

热门

文章归档

分类目录

功能