[LeetCode] 135. Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

分发糖果。

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是贪心。根据题意，我们需要对input数组扫描两遍，因为对于每个孩子来说，他拥有的糖果数需要同时和他的左右邻居比较以确保满足题意。所以我们创建两个和 input 数组等长的数组，left 数组从左往右扫描，right 数组从右往左扫描。

更新 left 数组的方式是，对于每个孩子，需要看他的评分是否大于他左边的孩子的评分，如果大于，当前这个孩子的糖果数起码是他左边孩子的糖果数 + 1

更新 right 数组的方式是，对于每个孩子，需要看他的评分是否大于他右边的孩子的评分，如果大于，当前这个孩子的糖果数起码是他右边孩子的糖果数 + 1

在更新 right 数组的同时，我们可以得到相同位置上 left 数组和 right 数组之间的较大值，这个较大值即是当前位置上的孩子需要拥有的糖果数

最后附上一个动图帮助理解。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public int candy(int[] ratings) {
		int n = ratings.length;
		int[] left = new int[n];
		int[] right = new int[n];
		Arrays.fill(left, 1);
		Arrays.fill(right, 1);
		for (int i = 1; i < n; i++) {
			if (ratings[i] > ratings[i - 1]) {
				left[i] = left[i - 1] + 1;
			}
		}

		for (int i = n - 2; i >= 0; i--) {
			if (ratings[i] > ratings[i + 1]) {
				right[i] = right[i + 1] + 1;
			}
		}

		int res = 0;
		for (int i = 0; i < n; i++) {
			res += Math.max(left[i], right[i]);
		}
		return res;
	}
}