# 冰镇

0%

## Description

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 #1 Two Sides Scan

### Intuition

Ratings:  12,  4,  3, 11, 34, 34,  1, 67

LeftScan:  1,  1,  1,  2,  3,  1,  1,  2
RightScan: 3,  2,  1,  1,  1,  2,  1,  1

Scan:      3,  2,  1,  2,  3,  2,  1,  2

### Algorithm

class Solution {
public:
int candy(vector<int>& ratings) {
int num[ratings.size()], sum = 0;
for (int i = 0; i < ratings.size(); i++) {
if (i == 0 || ratings[i-1] >= ratings[i]) {
num[i] = 1;
} else {
num[i] = num[i-1] + 1;
}
}
for (int i = ratings.size() - 1; i >= 0; i--) {
if (i + 1 < ratings.size() && ratings[i] > ratings[i+1]) {
num[i] = max(num[i], num[i+1] + 1);
}
sum += num[i];
}
return sum;
}
};

### Complexity Analysis

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

## Approach #2 Climb Scan

### Intuition

Ratings:  12,  4,  3, 11, 34, 34,  1, 67

Scan:      3,  2,  1,  2,  3,  2,  1,  2

Ratings: [1 2 3 4 5 3 2 1 2 6 5 4 3 3 2 1 1 3 3 3 4 2]

Ratings: 1, 2, 3, 4, 5, 3, 2, 1, 2
Up:      +  +  +  +
Down:                -  -  -

$CandyUp=\frac{(1+Up)*Up}{2}$

$CandyTop=Max(Up+1,Down+1)$

$CandyDown=\frac{(2+Down)*(Down-1)}{2}$

Ratings: 1, 3, 3, 3, 4, 2
Up:      +        +
Down:                -

### Algorithm

class Solution {
public:
int candy(vector<int>& ratings) {
int start = 0, sum = 0;
while (start < ratings.size()) {
int up = 0, down = 0;
while (start + 1 < ratings.size() && ratings[start] < ratings[start+1]) {
start++;
up++;
}
while (start + 1 < ratings.size() && ratings[start] > ratings[start+1]) {
start++;
down++;
}
if (up == 0 && down == 0) {
sum += 1;
start++;
continue;
}
sum += (1+up)*up/2 + (max(up, down)+1) + (2+down)*(down-1)/2;
}
return sum;
}
};

### Complexity Analysis

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。