[파이썬] 1299. Replace Elements with Greatest Element on Right Side

idx 0부터 n-1 까지 가면서

그 idx를 기준으로 오른쪽에있는 elements들 중 가장 큰 값을 arr[idx] 값으로 바꿔준다

=> 복잡도 O(N^2)

 

복잡도를 줄이기 위해서 idx를 n-2부터 0까지 가면서

그 idx를 기준 오른쪽에 있는 elements들 중 가장 큰 값을 구해준다.

=> O(N)

 

class Solution(object):
    def replaceElements(self, arr, mx=-1):
        for i in range(len(arr) - 1, -1, -1):
            arr[i], mx = mx, max(mx, arr[i])
        return arr