老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
这道题做的时间比较长，主要原因没有进行问题分解
解体思路是采用贪心算法，也就是求解问题不在整体上对问题进行考虑，而是做出多次局部最优解，最后将这些局部最优解组合得到最终解
假如学生A和学生B相邻，A在B的左边，我们可以将问题问题分解为两部分
- ratingB > ratingA，此时A的糖果要比B的少
- ratingB < ratingA，此时A的糖果要比B的多
我们不妨将这两种情况作为分发糖果的两个子问题，并且这两个子问题是互斥的
左规则：对于ratingA > ratingB，我们可以将rating从左到右遍历，如果rating[i] > rating[i-1]，那么rating[i] = rating[i-1] + 1，否则rating[i] = 1
不需要考虑左规则的学生，我们给他们分配最少1个糖果就可以了
右规则：对于ratingA < ratingB，我们可以将rating从右到左遍历，如果rating[i] > rating[i+1]，那么rating[i] = rating[i+1] + 1，否则rating[i] = 1
同时满足左规则和右规则时，我们可以相信糖果分配是合理的
但是我们还需要考虑糖果分配数量最优解的问题，也就是用最少的糖果满足题目条件
所以我们不能简单的将左规则和右规则分配的糖果相加得到最终解
我们可以这样思考最优解的问题：
- 最优解的糖果肯定是不能比左规则、右规则少的，否则就会破坏这两个条件其中一个
- 左规则和右规则之间有什么联系？
我们前面提到过不可能出现两个学生同时满足左规则和右规则的情况
所以说如果A的糖果比B的多，此时左规则分配的糖果为x1和y1，有x1<y1
同时A不需要满足右规则，也就是右规则分配的糖果x2=1，至于y2取任意之即可
那么我们就可以从这个关系切入，找出问题最优解
我们取x = max(x1, x2=1)，y = max(y1, y2)
x1=x<y，满足左规则，同时A和B又不需要考虑右规则
而且“最优解的糖果肯定是不能比左规则、右规则少的”，所以x、y就是问题的最优解
再来看时间复杂度，我们的左规则、右规则遍历了两边输入数组，最后将左规则和右规则结果遍历得到最终结果，所以时间复杂度O(n)
空间复杂度的话，实现左规则和右规则需要创建两个数组，所以空间复杂度为O(n)
下面是代码
/*
* @lc app=leetcode.cn id=135 lang=java
*
* [135] 分发糖果
*/
// @lc code=start
class Solution {
public int candy(int[] ratings) {
int[] leftCount = new int[ratings.length];
int[] rightCount = new int[ratings.length];
int len = ratings.length;
//左规则
for(int i=0;i<len;i++){
if(i>0&&ratings[i]>ratings[i-1]){
leftCount[i] = leftCount[i-1]+1;
}else{
leftCount[i] = 1;
}
}
//右规则
for(int i=len-1;i>=0;i--){
if(i<len-1&&ratings[i]>ratings[i+1]){
rightCount[i] = rightCount[i+1]+1;
}else{
rightCount[i] = 1;
}
}
//取最大值得到最终解
int ret = 0;
for(int i=0;i<len;i++){
ret += Math.max(leftCount[i], rightCount[i]);
}
return ret;
}
}
// @lc code=end