Hand Out Prizes So Higher Scorers Beat Their Neighbours
Implement minPrizes
A line of players each has a score. Prizes are handed out under two rules: everyone gets at least one prize, and a player who scores strictly higher than a neighbour standing directly next to them must get strictly more prizes than that neighbour. Find the fewest prizes that can be handed out.
Repeatedly repairing violations until none remain works but can ripple along a long descending run one step at a time. Splitting the rule into a left-neighbour half and a right-neighbour half, and satisfying each half in its own pass, gets the answer in two sweeps.
Example 1:
Input: scores = [1,3,6,5,4,2,3]
Output: 15
Example 2:
Input: scores = [3,3,3,3]
Output: 4
Example 3:
Input: scores = [5]
Output: 1
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ scores.length ≤ 15 and 0 ≤ scores[i] ≤ 9; the players stand in a line in the given order - ●
Every player must receive at least 1 prize - ●
If a player has a strictly higher score than a player standing directly next to them (left or right), they must receive strictly more prizes than that neighbour. Neighbours with equal scores have no such requirement - ●
Return the smallest total number of prizes that satisfies every rule
scores =