## 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:

Example 2:

## Approach #1 Two Sides Scan

### Complexity Analysis

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

## Approach #2 Climb Scan

### Intuition

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

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

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

### Complexity Analysis

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

0%