n + 1 people in a line, with places numbered from 0 (the very front) to n. You stand last, at place n. You are given an array fees of length n: the person at place i will swap places with you for fees[i].
Swaps work like this:
- you can swap with anyone **ahead** of you by paying their fee;
- you can swap with anyone **behind** you for free.
For every place i from 0 to n - 1, find the smallest total amount you must pay to end up at that place. Return an array of these n amounts.fees=[7, 9, 2, 6] → [7, 7, 2, 2]
Place 0 costs 7. Place 1 is cheaper through place 0 (7) than paying 9. Place 2 costs 2, and from there you can step back to place 3 for free, so the answer is [7, 7, 2, 2].
fees=[3, 5, 8] → [3, 3, 3]
Once you pay 3 for place 0, you can drop back to any place behind it for free.
fees=[4] → [4]
There is one person ahead, and place 0 costs 4.
n = fees.length ≤ 10⁵fees[i] ≤ 100fees=[7, 9, 2, 6]
[7, 7, 2, 2]
Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.