If you like C++ and STL, you may also like the following solution:

```
class Solution {
public:
int candy(vector<int> &ratings) {
// Corner case:
if (ratings.size( ) <= 1)
{
return ratings.size( ); // Zero or one.
}
vector<int> candies(ratings.size(), 1); // One candy per children at least.
extraCandies(begin(candies), end(candies), // Extra candies, left to right.
begin(ratings));
extraCandies(candies.rbegin(), candies.rend(), // Extra candies, right to left.
ratings.rbegin());
return accumulate(begin(candies), end(candies), 0); // Total summ of candies.
}
template<typename It>
int extraCandies(It candyIt, It candyEnd, It ratingIt)
{
int prevCandy = *candyIt;
int prevRating = *ratingIt;
while(candyIt != candyEnd)
{
if (*ratingIt > prevRating
&& *candyIt <= prevCandy)
{
// Bingo, extra candies for him!
(*candyIt) = prevCandy + 1;
}
prevRating = *ratingIt;
prevCandy = *candyIt;
++candyIt;
++ratingIt;
}
}
};
```

Complexity:

- CPU: O(n)
- Memory: O(n)