Candy

Problem

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?

---

Idea

• 第一步: 给每个小孩一个糖
• 第二步: 从左往右，只比较child i 和 child i-1， 如果 rating[i] > rating[i-1] && candy[i] < candy[i-1] 那么 candy[i] = candy[i-1]+1
• 第三步: 从右往佐, 只比较child i和child+1, 如果rating[i] > rating[i+1] && candy[i] < candy[i+1] 那么candy[i] = candy[i+1]+1

---

Solution

---