The issue is how to find "the next bigger integer on their right", which sounds like a stack operation.
Here is the algorithm in its essence.
- Create an empty stack.
- Iterate over the given list of integers from left to right.
- Push the current integer to the stack.
- While the top of the stack is smaller than the next integer in the list, replace the integer in the list that corresponds to the top of the stack by that next integer in the list followed by popping the stack.
The idea of the algorithm is to let the stack store the integers for which we have not found their next bigger integers yet, in the natural order in which they have been examined. Those integers will be strictly decreasing.
In the actual implementation, in order to locate the integer in the given list that corresponds to the top of the stack, the indices of the integers should be stored in the stack instead of the integer themselves.
Here is code in Python:
l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8, 5, 1 ,3, 8]
s = 
for i in range(len(l) - 1):
while s and l[i + 1] > l[s[-1]]:
l[s.pop()] = l[i + 1]
For readers who does not use Python,
s[-1] is the last element of the list
Since each index of the given list is appended once and popped at most once and the last index is not even included, the time-complexity of the algorithm is $O(n)$, where $n$ is the length of the given list.