> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/135.-candy.md).

# 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/)