Leetcode - 135. 分发糖果

class Solution {

    // 参考：https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/
    // 以输入[1, 2, 0, 4, 5]为例，先给所有孩子都分一颗糖果
    // 然后从左往右遍历：
    //  - 第二个孩子得分比第一个孩子高，因此第二个孩子的糖果必须比第一个孩子多1个，即2个
    //  - 第三个孩子得分比第二个孩子低，因此第三个孩子仍然是1个糖果
    //  - 依次类推，第四、五个孩子的糖果数分别是2和3
    //  - 因此得到一个数组[1, 2, 1, 2, 3]
    // 再从右往左遍历：
    //  - 第四个孩子得分比第五个孩子低，因此第四个孩子仍然是1个糖果
    //  - 以此类推，最终得到另一个数组[1, 2, 1, 1, 1]
    // 然后合并两个数组，取相同下标的两个元素的最大值，该值即为对应的孩子应该得到的糖果数
    public int candy(int[] ratings) {
        int length = ratings.length;
        int[] l2r = new int[length], r2l = new int[length];

        // 从左往右遍历，如果当前孩子得分高于左边孩子，则当前孩子的糖果数是左边孩子糖果数加1，否则只得到1个
        l2r[0] = 1;
        for (int i = 1; i < length; i++) {
            l2r[i] = ratings[i] > ratings[i - 1] ? l2r[i - 1] + 1 : 1;
        }
        
        // 从右往左遍历，如果当前孩子得分高于右边孩子，则当前孩子的糖果数是右边孩子糖果数加1，否则只得到1个
        r2l[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            r2l[i] = ratings[i] > ratings[i + 1] ? r2l[i + 1] + 1 : 1;
        }

        // Math.max(l2r[i], r2l[i])即为下标为i的孩子应该得到的糖果数
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += Math.max(l2r[i], r2l[i]);
        }
        return sum;
    }
}