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?

Analysis

• 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.

Code 1

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

Code 2

节省空间，只用一个额外空间，从右边扫描的时候用同一个array来存。注意update的条件有变化。

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] lc = new int[len];
        Arrays.fill(lc, 1);
        int res = 0;
        for (int i=1; i<len; i++){
            if (ratings[i]>ratings[i-1]) {lc[i]=lc[i-1]+1;}
        }
        for (int i=len-2; i>=0; i--){
            //注意这里判断条件变化很重要
            if (ratings[i]>ratings[i+1] && lc[i]<=lc[i+1]) {lc[i]=lc[i+1]+1;}
        }
        for (int i=0; i<len; i++){
            res += lc[i];
        }
        return res;
    }
}

Reference

Yu