leetcode: Candy

The idea is simple:

1. look for local minimum, assign 1 candy to local minimum.
2. Scanning from left to right, start from each local minimum, increase the candy by 1 if the rating increase. Cover all ascending "edge" from left to right;
3. Scanning form right to left, start from each local minimum, increase the candy by 1 if the rating increase. For local maximum, the candy number should be max of step2 and step3. After this, all ascending "edge" from right to left is covered.

How to find local minimum:

(no-bigger-than-left && no-bigger-than-right)

Note: Ratings can be equal so there can be some "flat" cases. 

In the requirement, it only says "higher rating, more candy than neighbors". What about "same rated neighbors"? Not necessarily same candies. Just make the total candies as less as possible!

Code

public class Solution {
    public int candy(int[] ratings) {
        
         int len = ratings.length;
        int[] candies = new int[len];
        
        if(len == 0) return 0;
        if(len == 1) return 1;
        //step1: find local minimum
        int i = 0;
        for(i = 0; i < len; i++)
        {
         if(i == 0 && ratings[i] <= ratings[i+1]) candies[i] = 1;
         if(i == len-1 && ratings[i] <= ratings[i-1]) candies[i] = 1;
         if(i > 0 && i < len-1 && ratings[i] <= ratings[i+1] && ratings[i] <= ratings[i-1]) candies[i] = 1;
        }
        
        //step2: assign candies
        for(i = 0; i < len-1; i++){
            if(candies[i] != 0 && ratings[i+1] > ratings[i]) candies[i+1] = candies[i] +1;
        }
        for(i = len-1; i > 0; i--)
        {
            if(candies[i] != 0 && ratings[i-1] > ratings[i])
                candies[i-1] = Math.max(candies[i-1], candies[i] + 1);
        }
        
        int total = 0;
        for(i = 0; i < len; i++)
            total += candies[i];
            
        return total;
    }
}