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?

Runtime: 392 ms

这道题跟Leetcode 一道contain water的题很像，思想很简单，可以把每个小朋友单独考虑，看下每个小朋友左边有紧邻的小朋友rate降序的个数，再看下该小朋友右边紧邻的小朋友降序的个数，然后就能确定本小朋友的最小“高度”（两降序个数中较大值），即为小朋友应得的糖果。

方法：从前往后，从后往前扫描两遍，并用lowleft[],lowright[]分别记录每个小朋友两边的降序个数即可~

public class Solution {

    public int candy(int[] ratings) {

        if(ratings.length==0) return 0;

        if(ratings.length==1) return 1;

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

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

        int ret=0;

        lowleft[0]=0;

        for(int i=1;i<ratings.length;i++){

            if(ratings[i-1]<ratings[i]) lowleft[i]=lowleft[i-1]+1;

            //else if(ratings[i-1]==ratings[i]) lowleft[i]=lowleft[i-1];

            else lowleft[i]=0;

        }

        lowright[ratings.length-1]=0;

        for(int j=ratings.length-2;j>=0;j--){

            if(ratings[j+1]<ratings[j]) lowright[j]=lowright[j+1]+1;

            //else if(ratings[j+1]==ratings[j]) lowright[j]=lowleft[j+1];

            else lowright[j]=0;

        }

        for(int i=0;i<ratings.length;i++){

            ret=ret+1+Math.max(lowright[i],lowleft[i]);

        }

        return ret;

    }

}