Candy, Leetcode 解题笔记

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?

初始化所有小孩糖数目为1,从前往后扫描,如果第i个小孩等级比第i-1个高,那么i的糖数目等于i-1的糖数目+1;从后往前扫描,如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等,那么i的糖数目等于i+1的糖数目+1。

该算法时间复杂度为O(N)

public class Solution {
    public int candy(int[] ratings) {
        int[] num = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            num[i] = 1;
        }
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                num[i] = num[i-1]+1;
            }
        }
        for(int i = ratings.length-2; i >= 0; i--){
            if(ratings[i] > ratings[i+1] && num[i] <= num[i+1]){
                num[i] = num[i+1]+1;
            }
        }
        int sum = 0;
        for(int i = 0; i < num.length; i++){
            sum += num[i];
        }
        return sum;
    }
}

这种两边扫描的方法是一种比较常用的技巧,LeetCode中Trapping Rain Water和这道题都用到了,可以把这种方法作为自己思路的一部分,通常是要求的变量跟左右元素有关系的题目会用到哈。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s