Well, you may need to run some examples to have the intuition for the answer since we only require children with higher rating get more candies than their neighbors, not all those with lower ratings.

The following code is taken from . It involves two-pass scan to ensure the above condition. You will get it after running some examples, like modifying the code and check the wrong cases :-)

1 class Solution { 2 public: 3     int candy(vector
     
      & ratings) { 4         int n = ratings.size(); 5         vector
      
        candies(n, 1); 6         for (int i = 1; i < n; i++) 7             if (ratings[i] > ratings[i - 1]) 8                 candies[i] = candies[i - 1] + 1; 9         for (int i = n - 1; i > 0; i--)10             if (ratings[i - 1] > ratings[i])11                 candies[i - 1] = max(candies[i - 1], candies[i] + 1);12         int total = 0;13         for (int i = 0; i < n; i++)14             total += candies[i];15         return total;16     }17 };