# 135. Candy

## LeetCode [135. Candy](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

There are `n` children standing in a line. Each child is assigned a rating value given in the integer array `ratings`.

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.

Return *the minimum number of candies you need to have to distribute the candies to the children*.

**Example 1:**

```
Input: ratings = [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: ratings = [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.
```

**Constraints:**

* `n == ratings.length`
* `1 <= n <= 2 * 10^4`
* `0 <= ratings[i] <= 2 * 10^4`

### Tags

Greedy

### Solution

#### Solution1:

We create an array, whose length is equal to `ratings` and all elements are initialized with 1, to store candies each child obtains. We first scan `ratings` from left, and if the right child has higher rating than that of the left child, we assign the number of candies owned by left child plus 1 to that of the right child. Then we perform the second scan from right. If the left child has higher rating than that of the right child, **and candies the left child owns is not more than that of the right child**, we assign the number of candies owned by right child plus 1 to that of the left child. Finally, we return the sum of candies array.

#### Solution 2:

![](/files/667w9JXdzUIX9xyG1HKM)

分发糖果总是从1开始并且增量为1。前后相邻两个孩子的评分相等或递增时如图，如果是递减的情况则需要看递减序列长度是多少（从开始下降的那个元素算起，不算上局部最大的元素），并且递减序列的最后一个孩子得到糖果数为1，则根据求和公式可以得到这段递减序列的糖果总数。

![](/files/b7Lc0MysU9NTQ1GXQBIz)

但还有一种情况是递减序列长度要大于等于之前的峰值，这时分发糖果数就要补充【递减序列长度-峰值+1】。

### Complexity

#### Solution1:

* Time complexity: $$O(n)$$
* Space complexity: $$O(n)$$

#### Solution 2:

* Time complexity: $$O(n)$$
* Space complexity: $$O(1)$$

### Code

#### Solution1:

```go
func candy(ratings []int) int {
	var ans int
	candies := make([]int, len(ratings))
	for i := range candies {
		candies[i] = 1
	}

	for i := 1; i < len(ratings); i++ {
		if ratings[i] > ratings[i-1] {
			candies[i] = candies[i-1] + 1
		}
	}
	for i := len(ratings) - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			candies[i] = max(candies[i], candies[i+1]+1)
		}
	}

	for _, c := range candies {
		ans += c
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
```

#### Solution 2:

```go
func candy(ratings []int) int {
	ans, pre, decNum := 1, 1, 0
	for i := 1; i < len(ratings); i++ {
		if ratings[i] >= ratings[i-1] {
			if decNum > 0 {
				ans += decNum * (decNum + 1) / 2
				if pre <= decNum {
					ans += decNum - pre + 1
				}
				pre, decNum = 1, 0
			}
			if ratings[i] == ratings[i-1] {
				pre = 1
			} else {
				pre++
			}
			ans += pre
		} else {
			decNum++
		}
	}
	if decNum > 0 {
		ans += decNum * (decNum + 1) / 2
		if pre <= decNum {
			ans += decNum - pre + 1
		}
	}
	return ans
}
```

## Reference

1. [LeetCode 101](https://github.com/changgyhub/leetcode_101)
2. [分发糖果](https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-powcai/)


---

# 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://txfs19260817.gitbook.io/leetcode-go-notes/solutions/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.