135. Candy
Question
There are
n
children standing in a line. Each child is assigned a rating value given in the integer arrayratings
.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.
Return the minimum number of candies you need to have to distribute the candies to the children.
Solution
双向遍历。
先从左至右遍历数组,如果上一个数值小于当前数值,则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组,同理计算right的数值。
然后保存right与left[]里较大的数值,作为需要分配的糖果数加入到res。
Code
1 | class Solution { |