hardGreedyPure DSA~35 min
Bonus Distribution By Rating
Engineers sit in a fixed review order, each with a performance rating. Every engineer must get at least one bonus unit, and anyone rated higher than an adjacent neighbor must receive strictly more than that neighbor. Minimize the total bonus paid.
Problem
Given an array ratings, assign each element a positive integer count so that any element with a higher rating than an adjacent neighbor gets a strictly larger count. Return the minimum total.
Input
An array ratings of n integers (1 ≤ n ≤ 2·10^4).
Output
An integer: the minimum total units distributed.
Constraints
- 1 ≤ n ≤ 2·10^4
- Each element receives at least 1 unit
- Equal adjacent ratings have no constraint between them
Examples
Example 1
Input
ratings = [1,0,2]
Output
5
Counts [2,1,2] satisfy the rules with total 5.
Example 2
Input
ratings = [1,2,2]
Output
4
Counts [1,2,1]; the equal pair needs no ordering.