Leetcode 135 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?

Solution 1: Use candy[n] to store the candies of each child. Sweep from begin to end then from end to begin to make requirements meet. At last, sum up all candies to result. O(n) time and O(n) space

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

Solution 2: O(n) time and O(1) space, sweep from begin to end. Use max and k to record recent high index and value.

 public class Solution {  
   public int candy(int[] ratings) {  
     int n=ratings.length;  
     if (n==0) return 0;  
     int k=0, max=1, val=1, res=1;  
     for (int i=1; i<n; i++) {  
       if (ratings[i]>ratings[i-1]) {  
         max=++val;  
         k=i;  
         res+=val;  
       }  
       else if (ratings[i]==ratings[i-1]) {  
         max=1;  
         val=1;  
         k=i;  
         res+=val;  
       }  
       else {  
         res+=i-k;  
         if (max<i-k+1) {  
           res+=i-k+1-max;  
           max=i-k+1;  
         }  
         val=1;  
       }  
     }  
     return res;  
   }  
 }