Pages

Tuesday 16 December 2014

Leetcode : Candy Java


Scan the rating array from left to right and then from right to left. In every scan just consider the rising order (l->r: r[i]>r[i-1] or r->l: r[i]>r[i+1]), assign +1 candies to the rising position.
The final candy array is the maximum (max(right[i],left[i])) in each position.
The total candies is the sum of the final candy array.

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

No comments:

Post a Comment