# 135.Candy

## 135. Candy

## 题目地址

<https://leetcode.com/problems/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)

```java
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

```java
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.

```java
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**

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/array/135.candy.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.