LeetCode_101_Candy

1. question: 分发糖果（困难）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

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

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

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

2. answers

这道题最开始想的是，遍历数组，每次与相邻元素进行比较，如果比任意相邻元素大，就比该元素分配多一个糖果。这个方法有一个致命的问题，就是当前元素比右侧的元素大的话，因为不知道右侧元素具体分配多少个糖果（这里可能会直观的认为是1，但是右侧元素可能还比右侧元素大，那么本右侧元素一定就不是1了），所以是没办法实现的，除非动态规划，后续返回更新。

参考了题解，分两次遍历。

1. 第一次遍历，从左到右，每次都比较是否比左侧元素大，如果大，就比该元素多分配一个糖果。
2. 第二次遍历，从右到左，每次都比较是否比右侧元素大，如果大，就比该元素多分配一个糖果。
3. 因为第一轮遍历，已经分配了基础糖果，并且也分配了比左侧元素大的元素的糖果。此时第二轮遍历，则就是解决上述初始思路的问题（因为已经为其分配了基础糖果，还分配了大的元素糖果），此时就是已经知道了其具体糖果，进行比较再分配即可。注意，此时已经比左侧大了，所以不会因为更新右侧，而导致左侧重新分配。因为右侧无论再怎么更新，只能变大，而不会变小，那么变大无论怎么变，还是会比左侧大的。

代码如下所示：

public class Solution_0101 {

    public int candy(int[] ratings) {

        if(ratings.length == 1) return 1;

        int[] counts = new int[ratings.length];
        int result = 0;

        // 与左侧元素比较
        for (int i = 0; i < ratings.length; i++) {

            counts[i] = 1;

            // 与左侧元素比较，如果大于他，则多分配一个。
            if(i > 0) {
                if(ratings[i] > ratings[i - 1]) counts[i] = counts[i - 1] + 1;
            }
        }

        // 与右侧元素比较
        for (int i = ratings.length - 1; i >= 0; i--) {

            // 与右侧元素比较，如果大于他，而且当前分配的也小于等于他，那么则比右侧元素多分配一个。
            // 因为此时是从后向前比较，那么只会在第一步的基础上修改比后面元素大的元素。
            if(i < ratings.length - 1) {

                if(ratings[i] > ratings[i + 1] && counts[i] <= counts[i + 1]) counts[i] = counts[i + 1] + 1;
            }
        }

        for(int i: counts) result += i;

        return result;
    }

    public static void main(String[] args) {

        Solution_0101 s = new Solution_0101();

        int[] ratings = {1,0,2};
//        int[] ratings = {1,2,2};
//        int[] ratings = {1,3,4,5,2};

        System.out.println(s.candy(ratings));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。