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?
左右各遍历一次，依据前一个位置的candy数计算当前位置需要的最小candy数（最少为1）
由于两次遍历的结果都要满足，因此对同一位置取max即可。
class Solution {
public:
int candy(vector<int>& ratings) {
if(ratings.empty())
return ;
int n = ratings.size();
vector<int> left(n, );
for(int i = ; i < n; i ++)
{
if(ratings[i] > ratings[i-])
left[i] = left[i-] + ;
}
vector<int> right(n, );
int sum = max(left[n-], right[n-]);
for(int i = n-; i >= ; i --)
{
if(ratings[i] > ratings[i+])
right[i] = right[i+] + ;
sum += max(left[i], right[i]);
}
return sum;
}
};