谈一道LeetCode——分发糖果
标题说明了一切，话不多说，开始正文吧！
分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
题目分析
先看题目要求，
1.每个孩子至少分配到 1 个糖果。
2.相邻的孩子中，评分高的孩子必须获得更多的糖果。
总的糖果最少
总结我们所有可能会遇到的情况，总的解决方法就是首先保证1越多越好，能发一个最好，之后以相差1的情况发放。
每个孩子至少一个糖果，那么什么样的情况孩子会得到一个糖果呢？
当这个孩子i，ratings{i] > ratings[i-1]，且ratings{i] < ratings[i+1]，边界可以单独考虑，简而言之就是处于“低谷”，“波谷”，以数学上的话来说，是函数的极小值。除此之外呢？
还有一种情况，连续的相同的值，而且是有条件的，例如，[1，2，3，3，2，1]，这种情况两个3处是1吗，不是，[1，2，3，3，3，2，1]，这种情况呢？
实际上，判断是不是发一个，可以这样想，如果上升之后就下降，就不是了，如果停留了，那可能是。
还有便是，连续的变化的时候，就是单调递增和递减时，以初始值为1，公差为 1 的等差数列发放
具体考虑便是，当单调递增时，初始值为1，当前发放的糖果比前一个多一个，如果到达了波峰，最高点，有可能下一个值补是最大值，有可能还是。
当不是最大值，意味着走“下坡路”了，此时，我们需要知道当前下降趋势走到了哪？将走到的地方记做极小值，此处发放一个糖果，以1的等差数列逆推之前的发放糖果数
如果还是最大值，但下一个不是最大值，其实处理方法跟之前一样
但是下下一个值还是最大值呢，那么下一个最大值为1
以几个个例子来看：
[1,2,3,2,1] ==> [1,2,3,2,1]
[1,2,3,3,2,1] ==> [1,2,3,3,2,1]
[1,2,3,3,3,2,1] ==> [1,2,3,1,3,2,1]
[1,2,3,3,3,3,3,2,1] ==> [1,2,3,1,1,1,3,2,1]
解题
首先用第一种方法，这种方法其实不是第一次用了，接雨水有一个方法和这个类似
使用两个vector<int> left,vector<int> right
一种从左到右记录“单调递增的序列”，实际是ratings的单调递增序列(从左到右)
另一种从右到左记录“单调递增的序列”，实际是ratings的单调递减序列(从左到右)
先举个例子：
ratings: [1,2,3,3,2,1,0,1,3,2,1]
left: [1,2,3,1,1,1,1,2,3,1,1]
right: [1,1,1,4,3,2,1,1,3,2,1]
汇总时，取两者的最大值就可以了
下面是程序：
class Solution {
public:
int candy(vector<int>& ratings) {
int len=ratings.size();
if(len==0){
return 0;
}
vector<int> left(len);
vector<int> right(len);
left[0]=1;
right[len-1]=1;
for(int i=1;i<len;i++){
if(ratings[i]>ratings[i-1]){
left[i]=left[i-1]+1;
}else{
left[i]=1;
}
}
for(int i=len-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
right[i]=right[i+1]+1;
}else{
right[i]=1;
}
}
int sum=0;
for(int i=0;i<len;i++){
sum+=max(left[i],right[i]);
}
return sum;
}
};
这是提交结果：
图片.png
由于提交有了一段时间，实际结果是，时间上还不错，但是空间上不佳
补：left[i]=1，这个地方似乎可以一开始给left赋初值。
其它解
接下来，我们使用另一种方法，不使用两个vector，边遍历边处理，过程稍微复杂了一点
具体过程和思路中基本一致，部分细节上有些差别，都在程序的注释里面了
下面是程序：
class Solution {
public:
int candy(vector<int>& ratings) {
int len=ratings.size();
if(len==0){
return 0;
}
//sum是总数，max_记下上一个评分的最高点
//down负责记录下降的位置
//count增加的糖果，连续上升或者下降时
//得到的糖果为1时，意味着该处i位于低谷 [i-1]>[i],[i]<[i+1],和连续多个相同的值，如2,2,2，此时中间的得到0个，但是两端的不确定，得看走势
int sum=1,max_=0,down=0,count=1;
for(int i=1;i<len;i++){
//下降
if(ratings[i-1]>ratings[i]){
if(down==0){
//在此之前的最高点
max_=count;
//记下评分开始下降的位置
down=i;
}
count=1;
//额外增加糖果
sum+=(i-down);
//波峰平稳处是否需要增加糖果，如果是，此处每个孩子得到的糖果为1
if(i-down+1>=max_){
sum++;
}
//上升
}else if(ratings[i-1]<ratings[i]){
down=0;
count++;
//平稳
}else{
down=0;
count=1;
}
sum+=count;
}
return sum;
}
};
下面是系统结果：
选区_003.png
图片.png
空间上有明显改善。
