题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例：
输入：ratings = [1,0,2]
输出：5

题目分析

贪心。
从左向右扫描一遍，ratings[i] > ratings[i-1] 时令 nums[i] = nums[i-1] + 1
再从右向左扫描一遍，ratings[i] > ratings[i+1] 时令 nums[i] >= nums[i+1] + 1

Java

public int candy(int[] ratings) {
    int[] nums = new int[ratings.length];
    for (int i = 0; i < ratings.length; i++) {
        nums[i] = 1;
        if (i - 1 >= 0 && ratings[i] > ratings[i - 1]) {
            nums[i] = nums[i - 1] + 1;
        }
    }
    int sum = 0;
    for (int i = ratings.length - 1; i >= 0; i--) {
        if (i + 1 < ratings.length && ratings[i] > ratings[i + 1]) {
            nums[i] = Math.max(nums[i], nums[i + 1] + 1);
        }
        sum += nums[i];
    }
    return sum;
}

Kotlin

fun candy(ratings: IntArray): Int {
    val nums = IntArray(ratings.size) { 1 }
    for (i in 1 until ratings.size) {
        if (ratings[i] > ratings[i - 1]) {
            nums[i] = nums[i - 1] + 1
        }
    }
    for (i in ratings.size - 2 downTo 0) {
        if (ratings[i] > ratings[i + 1]) {
            nums[i] = max(nums[i], nums[i + 1] + 1)
        }
    }

    return nums.sum()
}