135. Candy

Leetcode link

解题思路

本题要求我们给一排有排名的小朋友发糖果，规则有二：

1. 每个小朋友至少要给一颗糖
2. 相邻的小朋友如果有一方排名较高，则应该多给糖果

题目要求我们求出最少要给多少个糖果

我们可以拆分一下题目规则：

1. 当我们从左边往右边发糖果的时候，如果右边的小孩比左边排名高，则多给一颗糖，否则就给一颗糖
2. 当我们从右边网左边发糖果的时候，如果左边的小孩比右边的排名高，则多给一颗糖，否则就给一颗糖

所以我们只需要用两次遍历，然后在两种发糖果的方法中找出比较少的糖果组合返回就好

Javascript

var candy = function(ratings) {
    const len = ratings.length;
    const left = new Array(len).fill(1);
    let res = 0;

    for(let i = 0;i < len;i++) {
        if(i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }

    let right = 1;
    for(let i = len - 1;i >= 0;i--) {
        if(i < len - 1 && ratings[i] > ratings[i + 1]) {
            right++;
        } else {
            right = 1;
        }
        res += Math.max(right, left[i]);
    }

    return res;
};