Leetcode 135. 分发糖果

题干

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。

• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length

• 1 <= n <= 2 * 10^4

• 0 <= ratings[i] <= 2 * 10^4

初见

和 解法二 思路一样，但是写出来一团糨糊...

优化

解法一

遍历两次，第一次从左往右遍历，对于每相邻两个评分，右侧只要大于左侧，糖果便比左侧多 1，否则只获得 1个糖果；第二次从右往左遍历，对于每相邻两个评分，左侧只要大于右侧，糖果便比右侧多 1，否则只获得 1个糖果。取两次的最大值即为所求，因为最大值对于左侧与右侧必然同时满足两次的条件，即相邻两个孩子评分更高的孩子会获得更多的糖果。

class Solution {
    public int candy(int[] ratings) {
        int[] candiesLeft = new int[ratings.length];
        candiesLeft[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candiesLeft[i] = candiesLeft[i - 1] + 1;
            } else {
                candiesLeft[i] = 1;
            }
        }
        int[] candiesRight = new int[ratings.length];
        candiesRight[ratings.length - 1] = 1;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candiesRight[i] = candiesRight[i + 1] + 1;
            } else {
                candiesRight[i] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(candiesLeft[i], candiesRight[i]);
        }
        return sum;
    }
}

解法二

从左往右遍历，若评分为严格递增序列，则右侧孩子比左侧孩子的糖果多 1；若相邻两个评分相等，则右侧糖果数为 1；若评分为严格递减序列，则每多一个递减项，该项糖果数置 1 且该项左侧的所有递减项糖果数均 +1；注意若严格递增序列紧接着严格递减序列，且严格递减序列的项数大于等于严格递增序列的项数，则严格递增序列的最后一项自严格递减序列的项数与严格递增序列的项数相等那一刻起，也要参与到所有递减项糖果数 +1 这一步中。

class Solution {
    public int candy(int[] ratings) {
        int previous = 1, sum = 1, decrease = 0, increase = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                previous = (ratings[i] == ratings[i - 1]) ? 1 : previous + 1;
                sum += previous;
                increase = previous;
                decrease = 0;
            } else {
                decrease++;
                if (increase == decrease) {
                    decrease++;
                }
                sum += decrease;
                previous = 1;
            }
        }
        return sum;
    }
}