题解 | #分糖果问题#

/**
 * 解法：贪心
 * 思路：
 *   要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下大家都分到1, 
 *   相邻位置有增加的情况下，分到糖果数加1就好。什么情况下会增加糖果，相邻位置有得
 *   分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1?
 *   这不符合最小，必须从1开始加才是最小，那我们可以反向加1.
 * 时间复杂度：O(n)，单独遍历两次.
 * 空间复杂度：O(n)。记录每个位置糖果数的辅助数组.
 */
export function candy(arr: number[]): number {
    const len = arr.length
    if (len <= 1) return len
    let nums: number[] = []
    for (let i = 0; i < len; i++) {
        nums[i] = 1
    }
    for (let i = 1; i < len; i++) {
        if (arr[i] > arr[i - 1]) { // 如果右边在递增，每次增加一个
            nums[i] = nums[i - 1] + 1
        }
    }

    let res = nums[len - 1] // 记录总糖果数
    for (let i = len - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) { // 如果左边更大但是糖果树更小
            nums[i] = nums[i + 1] + 1
        }
        res += nums[i] // 累加和
    }

    return res
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview