Comment on page

# 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.

## 代码

### Approach #2 Using two arrays

Complexity Analysis
• Time complexity : O(n)
• Space complexity : O(n)
class Solution {
public int candy(int[] ratings) {
int sum = 0;
int[] left2right = new int[ratings.length];
int[] right2left = new int[ratings.length];
Arrays.fill(left2right, 1);
Arrays.fill(right2left, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) { // 右边大
left2right[i] = left2right[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) { // 左边大
right2left[i] = right2left[i + 1] + 1
}
}
for (int i = 0; i < ratings.length; i++) {
sum += Math.max(left2right[i], right2left[i]);
}
return sum;
}
}

### Approach #3 Using one array

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

### Approach 1: Brute Force

Complexity Analysis
• Time complexity : O(n^2). We need to traverse the array at most n times.
• Space complexity : O(n). One candies array of size n is used.
class Solution {
public int candy(int[] ratings) {
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
boolean flag = true;
int sum = 0;
while (flag) {
for (int i = 0; i < ratings.length; i++) {
if ( i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
flag = true;
}
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] < candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
flag = true;
}
}
}
for (int candy : candies) {
sum += candy;
}
return sum;
}
}
Approach #4 Single Pass with Constant Space Confused
public class Solution {
public int count(int n) {
return (n * (n + 1)) / 2;
}
public int candy(int[] ratings) {
if (ratings.length <= 1) {
return ratings.length;
}
int candies = 0;
int up = 0;
int down = 0;
int old_slope = 0;
for (int i = 1; i < ratings.length; i++) {
int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
candies += count(up) + count(down) + Math.max(up, down);
up = 0;
down = 0;
}
if (new_slope > 0)
up++;
if (new_slope < 0)
down++;
if (new_slope == 0)
candies++;
old_slope = new_slope;
}
candies += count(up) + count(down) + Math.max(up, down) + 1;
return candies;
}
}