/**

 * Source : https://oj.leetcode.com/problems/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?

 *

 */

public class Candy {

    /**

     * 给站成一排的孩子分糖果，

     * 每个孩子至少一个

     * 每个孩子的权重不一样，权重高的孩子比相邻的孩子要多

     * 求最少需要多少个糖果

     *

     * 从左到右遍历，寻找递增序列，该位置对应的孩子分的糖果数也递增，每个递增序列从1开始，这样保证了rating高的孩子比左边的孩子多

     * 然后从右向左遍历，确保当前位置孩子的糖果数多于右边孩子的

     * 复杂度为O(n)

     *

     * @param ratings

     * @return

     */

    public int candy (int[] ratings) {

        if (ratings.length <= 0) {

            return 0;

        }

        int[] candy = new int[ratings.length];

        candy[0] = 1;

        for (int i = 1; i < ratings.length; i++) {

            if (ratings[i] > ratings[i-1]) {

                candy[i] = candy[i-1] + 1;

            } else {

                candy[i] = 1;

            }

        }

        int sum = candy[ratings.length-1];

        for (int i = ratings.length-2; i > -1; i--) {

            if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) {

                candy[i] = candy[i+1] + 1;

            }

            sum += candy[i];

        }

        return sum;

    }

    public static void main(String[] args) {

        Candy candy = new Candy();

        int[] ratings = new int[]{5, 6, 7, 4, 1, 2, 3, 2, 1, 7};

        System.out.println(candy.candy(ratings) + " == 19");

    }

}