LeeCode 练习笔记：135.分发糖果-一一网

题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

示例 1：

输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
复制代码

示例 2：

输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
复制代码

我尝试利用面向对象的思想，深入浅出地分析这个题目，先给出可以通过测试用例的解决方案，然后逐步优化代码，最终找到最高效的解决方案。
既然题目中以“孩子”这一“天然对象”为载体，那就先给他 new 几个孩子出来，由于题目条件中要求“每个孩子至少分配到 1 个糖果”，所以先给每个孩子一人一颗糖果。
首先定义 Child 类

class Child {
    constructor(rating) {
        // 评分
        this.rating = rating;
        // 初始情况下，每人手里都有一颗糖
        this.candy = 1;
    }

    // 指定糖的数目
    setCandy(n) {
        this.candy = n;
    }
}
复制代码

假设入参ratings为[1,3,4,5,2]，我们现在开始分糖果，初始状态如下：

题目给我们的要求是要兼顾到每个孩子的两侧评分，所以这里可以按照贪心策略，在每次遍历中，只考虑并更新相邻一侧的大小关系，即，我们需要分别从左右两边来分别遍历一次，来完成分糖的过程。所以，我们将 “评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果”，拆分成 2 个策略：

从左数第2个孩子开始，往右遍历每个孩子，若该??比他左边?的孩子的评分分高，则将该??手里的糖数目更新为左边孩子糖数+1

为什么要从第二个孩子而不是从第一个孩子开始呢？这是因为我们从左到右遍历的目的，就是要让评分更高孩子手里的糖，都比他左边孩子手里的糖多，而第一个孩子左边没有人，所以他不需要参与这次遍历。
我们先不管第 2 个策略是什么，先走一遍程序看看是啥效果：
第2个孩子：

第3个孩子：

第4个孩子：

第5个孩子：

现在所有的评分更高孩子都比他左边孩子手里的糖要多了，现在我们再看另一侧的策略。

从右数第2个孩子开始，往左遍历每个孩子，若该??比他右边?的孩子的评分分高，且该??手里的糖数目，等于或少于右边孩子的糖数目时，才将该??手里的糖数目更新为右边孩子糖数+1

同样的道理，最后一个孩子的右边没有人，所以他同样不需要参与遍历，所以我们直接从右数第2个孩子开始遍历。注意在这条策略中的加粗部分，这是由于如果经历了上一次的遍历以后，更高评分的孩子的糖数，有可能已经比他右侧的孩子多了，所以这种情况下自然无需再更新他的糖数了。

至此，我们完成了分配过程，最后将每个孩子手里的糖果数量累加起来就能得到答案。代码如下：

class Child {
    constructor(rating) {
        this.rating = rating;
        this.candy = 1;
    }

    setCandy(n) {
        this.candy = n;
    }
}

var candy = function(ratings) {
    const children = ratings.map(rating=>{
        return new Child(rating);
    });

     // 从左往右遍历，若该孩子比他左边的孩子分高，则更新为左边孩子糖数+1
    for (let i = 1; i < children.length; i++) {
        let left = children[i - 1];
        let kid = children[i];
        if (kid.rating > left.rating) {
            kid.setCandy(left.candy + 1);
        }
    }

   // 从右往左遍历，若该孩子比他右边的孩子分高，且手里的糖等于或少于右边孩子，则更新为右边孩子糖数+1
    for (let i = children.length - 2; i >= 0; i--) {
        let right = children[i + 1];
        let kid = children[i];
        if (kid.rating > right.rating && kid.candy <= right.candy) {
            kid.setCandy(right.candy + 1);
        }
    }

    let res = 0;
    children.forEach(kid=>{
        res += kid.candy;
    })
    return res;
};
复制代码

但是上面的代码明显是我们为了具象化思考而特意设计的，它包含了对数组的4次遍历，并且引入了额外的对象，使得执行时间更长，占用内存空间也更多。它的效率差到啥地步呢？看下图就明白了。

接下来我们为了获得更高的执行效率，以及更少的内存占用，来对代码进行优化，首先由于 Child 类是为了具象化思考而特意设计的，所以可以直接使用2个数组来代替掉，节省内存空间，并且由于没有了额外的对象，也就自然不必再进行一次遍历来转换数据类型了，这样就又节约了一次遍历。

var candy = function(ratings) {
    const len = ratings.length;
    const candy = new Array(len).fill(1);

    // 从左往右遍历，若该孩子比他左边的孩子分高，则更新为左边孩子糖数+1
    for (let i = 1; i < len; i++) {
        let kid = ratings[i];
        let left = ratings[i - 1];
        if (kid > left) {
            candy[i] = candy[i - 1] + 1;
        }
    }
    // 从右往左遍历，若该孩子比他右边的孩子分高，且手里的糖等于或少于右边孩子，则更新为右边孩子糖数+1
    for (let i = len - 2; i >= 0; i--) {
        let kid = ratings[i];
        let right = ratings[i + 1];
        if (kid > right && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1;
        }
    }
    let res = 0;
    candy.map(candy=>res += candy);
    return res;
};

复制代码

嗯，效率已经提升了不少了，但是其实仔细分析一下还可以发现，最后那一次的为了累加计算而进行的遍历其实也可以节省掉。
思考如下：

在第一次分配遍历之后，我们已经得到了一个糖果数量的数列，而第二次分配遍历，是对该数列的一次调整，修改不符合要求的数字
从前面的分析可以知道，第一个孩子不参与第一次的遍历分配，最后一个孩子则不参与第二次的遍历分配，所以在第二次遍历分配之前，我们可以先给 res 赋上最后一个孩子的糖果数量作为初始值
累加发生在第二次遍历中的调整结束以后，所以完全可以将此过程放在第二次遍历过程中一起完成，而不需要单独再遍历一遍

由此可以继续将代码优化成下面的样子：

var candy = function(ratings) {
    const len = ratings.length;
    const candy = new Array(len).fill(1);

    // 从左往右遍历，若该孩子比他左边的孩子分高，则更新为左边孩子糖数+1
    for (let i = 1; i < len; i++) {
        let kid = ratings[i];
        let left = ratings[i - 1];
        if (kid > left) {
            candy[i] = candy[i - 1] + 1;
        }
    }
    // 最后一个孩子不参与第二次分配，故可以直接先赋值给 res 作为初始值
    let res = candy[candy.length - 1];
    
    // 从右往左遍历，若该孩子比他右边的孩子分高，且手里的糖等于或少于右边孩子，则更新为右边孩子糖数+1
    for (let i = len - 2; i >= 0; i--) {
        let kid = ratings[i];
        let right = ratings[i + 1];
        if (kid > right && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1;
           
        }
         res += candy[i]
    }
    return res;
};
复制代码