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

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

```cpp
// Two Pass Method
int candy(vector<int>& ratings) { // time: O(n); space: O(n)
    int n = ratings.size(), res = 0;
    vector<int> nums(n, 1);
    for (int i = 0; i < n - 1; ++i) {
        if (ratings[i + 1] > ratings[i]) nums[i + 1] = nums[i] + 1;
    }
    for (int i = n - 1; i > 0; --i) {
        if (ratings[i - 1] > ratings[i]) nums[i - 1] = max(nums[i - 1], nums[i] + 1);
    }
    // for (int num : nums) res += num;
    res = accumulate(nums.begin(), nums.end(), 0);
    return res;
}
```

{% hint style="info" %}
一開始給第一個人1個糖果，然後對於下一個人有三種情形。\
1\. 下一個人的rating == 前一個人的rating，給1個糖果就可以\
2\. 下一個人的rating > 前一個人的rating，比前一個人多給1個糖果\
3\. 下一個人的rating < 前一個人的rating，我們得計算連續遞減的ratings有多少個，最後可能需要再開始遞減的前一個人補糖果，因為假設後面遞減很多，那麼每個人減少一個糖果，可是題目條件限制每個人至少拿一個，也就是糖果數量不可以遞減至少於0。可以用例子:\[1, 3, 2, 1]來想想，一開始給第一個人1個，第二個人給2個的話，這樣會不夠，所以最後需要補上一些糖果。
{% endhint %}

```cpp
// One Pass Method
int candy(vector<int>& ratings) { // time: O(n); space: O(1)
    if (ratings.empty()) return 0;
    // pre: the candies for the student before this descending sequences of students
    // cnt: the number of descending ratings except the first one in the descending sequence
    int res = 1, pre = 1, cnt = 0;
    for (int i = 1; i < ratings.size(); ++i) {
        if (ratings[i] >= ratings[i - 1]) {
            if (cnt > 0) {
                res += cnt * (cnt + 1) / 2;
                if (cnt >= pre) res += cnt - pre + 1;
                cnt = 0;
                pre = 1;
            }
            pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
            res += pre;
        } else {
            ++cnt;
        }
    }
    if (cnt > 0) {
        res += cnt * (cnt + 1) / 2;
        if (cnt >= pre) res += cnt - pre + 1;
    }
    return res;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://jimmylin1991.gitbook.io/practice-of-algorithm-problems/greedy/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.