【一天一大 lee】分发糖果 (难度:困难) - Day20201224

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

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

// 评分
ratings = [1, 0, 2]
// 糖果
left = [1, 1, 2]

// 评分
ratings = [1, 0, 2]
// 糖果
left = [1, 1, 2]
// 从右向左遍历
right = [2, 1, 1]

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let len = ratings.length,
        _result = 0,
        left = Array(len).fill(0),
        right = Array(len).fill(0)
    // 特殊情况
    if (len === 0) return _result
    // 先从左向右遍历：保证左侧评分高糖果数大于右侧（递增数量）
    for (let i = 0; i < len; i++) {
        if (i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1
        } else {
            left[i] = 1
        }
    }
    // 再从右向左遍历：保证右侧评分高糖果数大于左侧（递减数量）
    for (let i = len - 1; i >= 0; i--) {
        if (i < len - 1 && ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1
        } else {
            right[i] = 1
        }
        _result += Math.max(left[i], right[i])
    }
    return _result
}

            5
        3       4
    1               3
                        2
                            1
    1   2   3   2   1   0   0   再向后发数递增元素数量将和递减元素数量相同，如果不做任何处理那么此时2位置要发0个糖，不满足题意
    1   2   4   3   2   1   0   递减片段中（包括转折处的最大值）的每个元素要多发一个糖
    1   2   5   4   3   2   1   递减片段中（包括转折处的最大值）的每个元素要多发一个糖

var candy = function(ratings) {
    let len = ratings.length,
        _result = 0,
        num = 1, // 最近已统计的连续递增片段计数
        reduceNum = 0, // 遇到连续递减元素数量
        increaseNum = 1 // 遇到连续递增元素数量

    for (let i = 1; i < len; i++) {
        // 元素递增
        if (ratings[i] >= ratings[i - 1]) {
            reduceNum = 0
            // 相同时，递增计数重置为1，作为新片段起点
            if (ratings[i] === ratings[i - 1]) {
                increaseNum = 1
            } else {
                increaseNum++
            }
            _result += increaseNum
            num = increaseNum
        } else {
            // 元素递减
            reduceNum++
            // 如果连续递减片段元素个数出现等于递增个数时（如果保持每次递减糖果数-1次数将会出现0个糖果的元素），那么需要递减片段中（包括转折处的最大值）的每个元素要多发一个糖
            if (reduceNum === num) reduceNum++
            _result += reduceNum
            increaseNum = 1
        }
    }
    return _result
}