leetCode解题报告之Candy（简单回溯）

柔光的暖阳◎ 2022-08-26 04:44 157阅读 0赞

**题目：**

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值，小孩子站成一排，这时候rating值按顺序放入到数组中，

主人公要给N个小孩子发糖果，但是又抠门，想要尽量最少的糖果被发出！要满足如下两个条件：

1、每个孩子最少都要有一个糖果

2、拥有比较高的rating值的孩子要比自己身边的孩子得到的糖果多

**解题思路：**

由于这两个条件，我们需要考虑到如果rating值和相邻两边的rating值相等的情况，我们只需分配1个糖果给这个孩子就可以了

如：ratings = \{1,2,2,2,3,2,1\};

我们最少要分配的糖果candys = \{1,2,1,1,3,2,1\} = 11个糖果

但是我们如果想要确定ratings 数组中 rating值为“3”的这位孩子所得到的糖果，我们又必须知道后面的情况，所以我们需要用到回溯法.具体看如下AC代码：

AC代码：

/*
    时间复杂度：O(n)
    空间复杂度: O(n)
    */
    public class Solution {
        public int candy(int[] ratings) {
            int len = ratings.length;
            if (len == 0)
                return 0;
            int sum = 0;
            int[] candys = new int[len];
            
            /*简单初始化各个孩子所得到的糖果数,如果比自己的前一个孩子rating值高，则等于前一个孩子的糖果数+1，否则等于1*/
            for (int i=0; i<len; ++i){
                 if (i == 0){
                    candys[i] = 1;
                    continue;
                 }
                 if (ratings[i] > ratings[i-1]){
                     candys[i] = candys[i-1] + 1;
                 }else{
                     candys[i] = 1;
                 }
            }
            
            /*计算总共需要的最少糖果数*/
            int total = candys[len-1];  //先把最后一个children的糖果数加上来
            for (int i=len-2; i>=0; --i){
                //回溯调整
                if (ratings[i] > ratings[i+1] && candys[i+1]+1 > candys[i]){
                    candys[i] = candys[i+1]+1;
                }
                total += candys[i];
            }
            return total;
        }
    }