Standard Bar Greedy Approach · Medium O(n) · O(n)
A firm lines up employees for performance bonuses along a corridor, each with a review score. HR rules: everyone receives at least one bonus unit, and anyone scoring higher than an immediate neighbor must receive strictly more than that neighbor. Finance wants the smallest legal total payout, computed in two smoothing passes along the line.
Input: An integer array ratings of review scores.
Output: Return the minimum total units required to satisfy both rules.
1 <= ratings.length <= 2 * 10^40 <= ratings[i] <= 2 * 10^4Input: {"ratings":[1,0,2]}
Output: 5
Payouts 2, 1, 2 satisfy both neighbor rules at minimum total.
Input: {"ratings":[1,2,2]}
Output: 4
The tie between the last two needs no differentiation: 1, 2, 1 suffices.