1796. Running Podium Total
A diving contest posts judges' scores one at a time, and the broadcast always shows a podium total: the sum of the three highest scores received so far, or the sum of all of them while fewer than three scores exist. Scores may be negative because of penalties, and equal scores are counted separately.
Given the array nums of scores in arrival order, return a long[] whose entry i is the podium total right after nums[i] arrives. Keep only the three best scores in a small min-heap so each arrival is handled in constant time: O(n) time and O(1) extra space besides the output.
Example 1
- Input:
- nums = [5,2,9,1,7]
- Output:
- [5,7,16,16,21]
- Explanation:
After the scores 5, 2, 9 the podium is 16; the late 7 pushes out the 2, giving 9 + 7 + 5. The answer is [5, 7, 16, 16, 21].
Example 2
- Input:
- nums = [-3,-1,-4]
- Output:
- [-3,-4,-8]
- Explanation:
With fewer than three scores every score counts, negative or not, so the totals are [-3, -4, -8].
Example 3
- Input:
- nums = [10,10,10,10]
- Output:
- [10,20,30,30]
- Explanation:
Equal scores count separately, so the total stops growing at three tens: [10, 20, 30, 30].
Constraints
1 ≤ n ≤ 300
-106 ≤ nums[i] ≤ 106
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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)