题解 | #分糖果问题#

贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

如何使用贪心思想解决分糖果问题

• 利用贪心思想，初始时每个人都获得一个糖果，然后遍历每个人和相邻的人的分数进行比较，如果比周围人的分数高，则糖果数应该比周围的人多一个，如果比周围人的分数少，周围人的糖果数应该比这个人的糖果数多一个，但是周围人的糖果数一旦改变，与周围人相邻的其他人的糖果数也要随之改变，否则会出现糖果数量比相邻人多出超过一个的情况。
• 由于周围分为左边相邻的人和右边相邻的人，我们可以先从左到右遍历，和左边相邻的人比较，然后右边比左边的人分数高时更新糖果数量，从左到右遍历完后，由于没有考虑和右边相邻的人的比较，因此左边的人可能会有比右边的人分数高的情况，此时需要从右到左遍历，和右边的人比较，在左边的人比右边的人分数高时修正糖果数量。

参考

https://blog.nowcoder.net/n/67103981f23d4a87a2949d3550e421c2?f=comment

https://blog.nowcoder.net/n/aff3f403aeaf43baa73e35253f71b325?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * pick candy
 * @param arr int整型一维数组 the array
 * @return int整型
 */
export function candy(arr: number[]): number {
    // write code here
    const dp: number[] = new Array(arr.length).fill(1);
    let sum = 0;

    for (let i = 1; i < arr.length; ++i) {
        if (arr[i] > arr[i-1]) {
            dp[i] = dp[i-1] + 1;
        }
    }

    for (let i = arr.length-2; i >= 0; --i) {
        if (arr[i] > arr[i+1] && dp[i] <= dp[i+1]){
            dp[i] = dp[i+1] + 1;  // dp[i-1]更新了，i-1之前的糖果数也应更新，否则有可能不满足邻近分数高的孩子糖果数多一个的要求
        }
    }

    dp.forEach(item => sum += item);
    return sum;
}