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?

这道题就是从左往右和从右往左分别扫两次,因为requirement里面说需要一个rating高的需要比rating低的拿到的candy多
第一遍从左往右,如果rating一直升高,那么发的candy数max也必须一直升高,如果降低,则设为0
第二遍从右往左,如果rating一直升高,那么发的candy数max也升高,但是如果第一遍扫出来的结果已经高于max,则不需要加,如果降低则维持第一遍扫的结果。
最后给所有的人都发一个糖,(result+ratings.length)即可。

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

Second submission:

public class Solution {
    public int candy(int[] ratings) {
        int [] dp = new int [ratings.length];
        int max = 0;
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i-1]) {
                max++;
            }
            else 
                max = 0;
            dp[i] = max;
        }
        max = 0;
        for (int i = ratings.length - 2; i >=0; i--) {
            if (ratings[i] > ratings[i+1]) {
                max++;
            }
            else 
                max = 0;
            dp[i] = Math.max(dp[i], max); // id dp[i] already larger than max, no need to change
        }
        int result = 0;
        for (int i = 0; i < ratings.length; i++) {
            result += dp[i];
        }
        
        return result + ratings.length;
    }
}

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