/**
 * 解法:贪心
 * 思路:
 *   要想分出最少的糖果,利用贪心思想,肯定是相邻位置没有增加的情况下大家都分到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