谈一道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

空间上有明显改善。