Candy

Q:
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?

A:
--------------------1st pass--------------------------------
 简直TMD被忽悠了。  没想到如此地简单。
solution 就是简单的一遍遍地遍历，然后，看是否有变化， 有需要变化的，则改之。

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int arrCandy[] = new int[n];
        Arrays.fill(arrCandy,1);
        boolean changed = true;
        while(changed){
            changed = false;
            for(int i =1;i<n;i++)
                if(ratings[i]>ratings[i-1] && arrCandy[i]<=arrCandy[i-1]){
                    arrCandy[i]=arrCandy[i-1]+1;
                    changed = true;
                }
            for(int i=n-2;i>=0;i--)
                if(ratings[i]>ratings[i+1] && arrCandy[i] <= arrCandy[i+1]){
                    arrCandy[i] = arrCandy[i+1]+1;
                    changed=true;
                }
        }
        int sum = 0;
        for(int i =0;i<n;i++)
            sum+=arrCandy[i];
        return sum;
    }
} 

-----------------------这个方法，关键的地方是在左右两边分别按照ascending 和descending来做。
这样就排除了一些极端的情况。而如果是random的数的话，很快就排好了。

--------------第二遍---------------while里，只用了一个for 循环， 里面处理了两种情况---------导致一些ratings = 1 到2000 时， 会TLE

------------------Solution 2---------------来自网上----
初始化所有小孩糖数目为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 n = ratings.length;
        int[] nCandy = new int[n];
        Arrays.fill(nCandy,1);
            
        for(int i =1;i<n;i++)
            if(ratings[i]>ratings[i-1])
                nCandy[i]= nCandy[i-1] +1;
                
        for(int i = n-1;i>0;i--)
            if(ratings[i-1] > ratings[i] && nCandy[i-1] <= nCandy[i] )
                nCandy[i-1]= nCandy[i] +1;
                
        int count = 0;
        for(int i = 0;i<n;i++)
            count += nCandy[i];
        return count;
    }
}

Learned:



6： 哎，
 int i ;
for(i =0;i<5;i++){
}
System.out.println(i); -----------> 结果是5