LeetCode-135-分发糖果

题目描述：n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

题目详细链接

解题思路：
这道题既要考虑左孩子和自己的大小，还要考虑右孩子和自己的大小，两边都要满足，一次遍历不能两者兼顾，因此需要遍历两次，一次考虑 右孩子 > 左孩子的情况，一次考虑 左孩子 > 右孩子的情况。
具体步骤如下：

1. 构建一个糖果数组candy []，长度和孩子数组一样，初始值都是1；
2. 先从左到右遍历 考虑 右小孩 > 左小孩 的时候右小孩糖果+1的情况
3. 再从右到左遍历 考虑 左小孩 > 右小孩 的时候左小孩糖果+1的情况，为什么需要从右向左遍历，自己推理一下就可以理解了，注意，这个是在上一步的基础之上更新candy []，因此要选择两次的最大值作为最终的candy[i]结果
4. 对candy []求和返回结果即可。

代码实现：

class Solution {public int candy(int[] ratings) {int len = ratings.length;int[] candy = new int[len];// ，每个孩子需要的糖果数组// 初始化糖果为 1for (int i = 0; i < len; i++) {candy[i] = 1;}// 先从左到右遍历 考虑 右小孩 > 左小孩 的时候右小孩糖果+1的情况for (int i = 1; i < len; i++) {if (ratings[i] > ratings[i-1]){candy[i] = candy[i-1]+1;}}// 再从右到左遍历 考虑 左小孩 > 右小孩 的时候左小孩糖果+1的情况for (int i=len-1;i>0;i--){if (ratings[i-1] > ratings[i]){candy[i-1] = Math.max(candy[i] + 1, candy[i-1]);// 因为第一次从左向右遍历的时候已经有值了，所以这次取最大值}}int res = 0;for (int i = 0; i < len; i++) {res += candy[i];// 这种方法的耗时更短}return res;
//        return Arrays.stream(candy).sum();//数组求和，但是效率低}
}