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?

[解题思路]

two pass scan, one pass from left to right, next pass from right to left

when find increment sequence, set candy by k, then increment k

something need to attention, the requirement of this problem is that only children with a higher rating need to get more

candies than their neighors, but if two child has the same rating, we do not need to give more candies

the time complexity is O(n), the space complexity is also O(n)

1 public class Solution { 2     public int candy(int[] ratings) { 3         int N = ratings.length; 4         if(N == 0){ 5             return N; 6         } 7         int[] candy = new int[N]; 8         int sum = N; 9         for(int i = 0, k = 1; i < N; i++){10             if(i - 1 >= 0 && ratings[i] > ratings[i - 1]){11                 candy[i] = Math.max(k ++, candy[i]);12             } else {13                 k = 1;14             }15         }16         17         for(int i = N - 1, k = 1; i >= 0; i--){18             if(i + 1 < N && ratings[i] > ratings[i + 1]){19                 candy[i] = Math.max(k ++, candy[i]);20             } else {21                 k = 1;22             }23         }24         25         for(int i = 0; i < N; i++){26             sum += candy[i];27         }28         return sum;29     }30 }