135. 分发糖果 - 力扣（LeetCode）

一、题目

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 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

二、代码

class Solution {
    public static int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }

        // 构造预处理数组
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        
        // 从左向右构造
        left[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            // 我们不管相邻两个数相等的情况，题目要求最少准备多少个，所以碰到相等或小于相邻人的情况下，直接赋值为1，这样就能取得最少准备的个数。    
            } else {
                left[i] = 1;
            }
        }

        // 从右向左构造
        right[ratings.length - 1] = 1;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i + 1] < ratings[i]) {
                right[i] = right[i + 1] + 1;
            } else {
                right[i] = 1;
            }
        }

        // 取每个位置的最大值，就能保证题目的要求
        int sum = 0;
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(left[i], right[i]);
        }

        return sum;
    }
}

三、解题思路 

从左边开始，向右生成left数组，left数组代表每一个点左边的坡度。
下标0位置左边没东西，所以给他发1块糖，后续位置只要是得分比左边大，发糖数就比左边的人加1个，如果碰到得分不再大了，发糖数就重新给1，再从1开始++。

从右边开始，向左生成right数组，right数组代表每一个点右边的坡度。
下标n-1位置右边没东西1块糖，剩余的小朋友比右边大了了就++，不再大了就回到1。

left数组和right数组对应的每个位置的max就是这个位置的小朋友应该分糖数量，将每个位置要分糖得数量累加就是最终要准备的糖的总数。左坡和右坡以较大坡为准，因为这样才能保证如果分数比左右两边得大，拿得到糖比左右两边的人都多。