题解 | #分糖果问题#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * pick candy
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function candy(arr) {
    // write code here
    //先将数组排序
    //局部最优：只要后面一个人比前面一个数大，就多一个糖果，否则就跟前面的人一样
    let res = [];
    for (let i = 0; i < arr.length; i++) {
        res[i] = 1;
    }

    //右边比左边大(从前往后比较)
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] > arr[i]) {
            res[i + 1] = res[i] + 1;
        }
    }

    //左边要比右边大(从后往前比较)
    for (let i = arr.length - 1; i >= 0; i--) {
        if (arr[i + 1] < arr[i]) {
            if (res[i] == res[i + 1] || res[i] < res[i + 1]) {
                res[i] = res[i + 1] + 1;
            }
        }
    }

    let sum = 0;
    for (let item of res) {
        sum += item;
    }

    return sum;
}
module.exports = {
    candy: candy,
};