[数据结构与算法]Java描述 LeetCode，135. Candy 分发糖果

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

1-1：题目

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.
Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy

1-2：自己的idea

??我自己的想法是一次遍历，同时考虑i-1,i,i+1这三个位置，比如ratings=[2,1,5]分别分发candy=[2,1,2]，但是想了下，错喽，比如[2,1,5,3,2,1]就会发现，1这个没法分了，所以说考虑两边的时候，必定会受其他的影响，这个例子就可以很好的说明这个问题。

1-2：解法1

1-2-1：idea

??同时考虑两边不行，那有一种办法就是先考虑一边，如果右边的rating比左边的大，就分配右边的多一个糖果。这样一轮下来就可以保证，一边局部满足题意。只要在从右向左进行遍历，如果左边的rating比右边的大，就分配左边的比右边的多一个糖果。但是要注意，第二轮的值不能比第一轮的值小，不然就不能满足第一轮的局部最优了，这边可以画个表试一下，你就懂我的意思了，比如：ratings = [1, 2, 2, 5, 4, 3, 2]第一轮[1, 2, 1, 2, 1, 1, 1]第二轮[1, 2, 1, 4, 3, 2, 1]，还有一个注意点，相同的rating，不用多分糖果，从这个例子就可以看出来，（这是题目的一个潜规则）

1-2-2：代码

public static int candy(int[] ratings) {
    int n = ratings.length;

    int[] candyDeliver = new int[n];
    for (int i = 0; i < n; i++) {
        candyDeliver[i] = 1;
    }


    for (int i = 1; i < n; i++) {
        // right > left
        if (ratings[i] > ratings[i - 1]) {
            // assert the right child's candy > the left
            candyDeliver[i] = candyDeliver[i - 1] + 1;
        } else {
            // keep one
        }
    }

    for (int i = n - 1; i >= 1; i--) {
        // left > right
        if (ratings[i] < ratings[i - 1]) {
            candyDeliver[i - 1] = Math.max(candyDeliver[i] + 1, candyDeliver[i - 1]);
        } else {
            // keep original to use former result
        }
    }

    System.out.println(Arrays.toString(candyDeliver));

    int sumCandy = 0;
    for (int candy : candyDeliver) {
        sumCandy += candy;
    }
    return sumCandy;
}

1-3：解法2

1-3-1：idea

??这个解法也来自于答案，他是巧妙的运用了升序和降序的思想，把一整个数组分割成很多个小的递增/递减小数组，因为数字之间必定有大小。

1-3-2：代码

    public static int candy2(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                // 出现递增的时候，就要重置降序序列的长度为0
                dec = 0;
                // 更新pre的值
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                // pre就是i这个位置的同学分配的糖果
                ret += pre;
                // pre的值等于递增序列的长度
                inc = pre;
            } else {
                dec++;
                // 为什么有这个呢？长度相等的时候，递增序列的最后一个就会变成递减序列的成员。
                // 比如rating = [1,3,5,3,2,1] 增加的糖果依次为1,2,3,1,2,4；特别是4这个位置，4是
                // dec== inc ==3的时候，把前面的3当做是降序的成员，我自己由3变成4.虽然分发的顺序不符合
                // 小孩的位置，但是不影响总的计数。实际分发应该是[1,2,4,3,2,1]这个顺序。
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                // pre只在递增的时候用到
                pre = 1;
            }
        }
        return ret;
    }

需要解释的都在注释里面啦！可以自己单步debug下就可以知道里面的过程变化了，或者对比下力扣里面的题解就可以了。

1-4：总结

??答案的思想是想不到的，算是一种积累，刷题多积累点，万一遇到原题呢~