Formatted question description: https://leetcode.ca/all/135.html
135 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?
First initialize one candy for each person, and then the algorithm needs to traverse twice
- the first traverse from left to right, if the level of the small pot on the right is high, one more candy to be added, which ensures that there are more candies in left-to-right direction.
- Then it traverses from right to left again. If the two adjacent left sides have a higher level and the left side has fewer candies, the number of candies on the left is the number of candies on the right plus one. Finally, add up the number of candies of all the friends
My idea is to use four test cases: ratings:
- Monotonous increase: 7,8,9
- Monotonic reduction: 9,8,7
- Wave shape: 7,8,9,8,7
- Wave trough shape: 9,8,7,8,9