224. Candy
Hard
Two-Pass Greedy
Array
Problem
There are n children standing in a line, each with a rating. Every child must receive at least one candy, and children with a higher rating than an adjacent child must receive more candies than that child. Return the minimum total number of candies required.
Examples
Example 1
Input: [1,0,2]
Output: 5
Example 2
Input: [1,2,2]
Output: 4
Example 3
Input: [1]
Output: 1
Constraints
� 1 <= ratings.length <= 100000
� 0 <= ratings[i] <= 100000
Hints
?? One pass can satisfy the left-neighbor requirement.
?? A reverse pass can satisfy the right-neighbor requirement.
?? Take the maximum requirement from both directions.
Expected Complexity
Time: O(n)
Space: O(n)
Follow-up
Can you derive an O(1) extra-space slope-based solution?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,0,2]Expected
5