575. Candy Line
A teacher lines up n pupils for a prize draw, where ratings[i] is the effort score of the pupil at position i. Every pupil must receive at least one sweet, and whenever a pupil has a strictly higher score than the pupil standing directly left or directly right, that pupil must receive strictly more sweets than that neighbour. Equal scores impose no restriction on each other.
Return the smallest total number of sweets that satisfies all the rules.
Do it in O(n) time. Repeatedly fixing violations until nothing changes can need about n rounds on a long descending run and is far too slow. The answer is guaranteed to fit in a 32-bit signed integer because n is bounded.
Example 1
- Input:
- ratings = [2,5,5,1]
- Output:
- 6
- Explanation:
The sweets 1, 2, 2, 1 satisfy the rules: the second pupil beats the first, the third beats the fourth, and the equal middle pair is unconstrained.
Example 2
- Input:
- ratings = [4,3,2,1,5]
- Output:
- 12
- Explanation:
The descending run needs 4, 3, 2, 1 sweets from left to right and the last pupil needs 2, for a total of 12.
Example 3
- Input:
- ratings = [7,7,7]
- Output:
- 3
- Explanation:
All scores are equal, so each pupil needs only the minimum single sweet.
Constraints
1 ≤ ratings.length ≤ 600000 ≤ ratings[i] ≤ 1000000000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)