糖果问题.md

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?

有n个小孩站成了一行，每一个孩子都有一个等级值，你现在要给这些孩子按照以下原则分糖果：

每一个小孩必须最少分到一个糖果； 拥有更高等级值的孩子必须比他相邻的孩子分的糖果多。

请问你最少需要多少糖果？

解题思路

rating={1,2,5,3,9,2} candyArray={1,1,1,1,1,1} 采用只加不减的策略，扫描2遍： 第一遍从左向右扫描，保证右边孩子如果优先级比左边孩子大就让右边孩子的糖果数比左边孩子多1，这样可以保证从左到右孩子的糖果分布式符合要求的； 第二标从右向左扫描，保证左边孩子如果优先级比右边孩子大就让左边孩子的糖果数比左边孩子多1，这样可以保证从右到左孩子的糖果分布式符合要求的； 走完上面两步之后，可以保证不管是从左往右走还是从右往左走，孩子们的糖果分配都是符合要求的，最后将candyArray求和返回即可。

代码

核心代码：

public int candy(int[] ratings) {


        int n = ratings.length;
        int[] candyArray = new int[n];
        //第0个孩子初始分配1个糖果
        candyArray[0] = 1;
        for (int index = 1; index < ratings.length; index++) {

            //如果右边孩子的优先级大于左边孩子的优先级
            if (ratings[index] > ratings[index - 1]) {
                //右边孩子分配的糖果数更新为左边孩子分配的糖果数加1
                candyArray[index] = candyArray[index - 1] + 1;
            } else {
                //如果右边孩子的优先级不大于左边孩子的优先级，将右边孩子的糖果数分配为1
                candyArray[index] = 1;
            }
        }

        int sum = candyArray[ratings.length - 1];
        for (int index = ratings.length - 2; index >= 0; index--) {
            //如果左边孩子的优先级大于右边孩子的优先级且左边孩子分配的糖果小于等于右边孩子分配的糖果
            if (ratings[index] > ratings[index + 1] && candyArray[index] <= candyArray[index + 1]) {
                //左边孩子分配的糖果数更新为右边孩子的糖果数加1
                candyArray[index] = candyArray[index + 1] + 1;
            }
            sum += candyArray[index];
        }
        return sum;
    }

这里