注意这里的右边不包括该位置上的元素。

自己解法：动态规划

设新列表为res，原列表为arr，初始状态为：

• res[-1] = -1
• res[-2] = arr[-1]

下标从len(arr) - 2递减至0，转移方程为：

python">if arr[i+1] > res[i+1]:
	res[i] = arr[i+1]
else:
	res[i] = res[i+1]

Python实现：

python">class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        if len(arr) == 1:
            return [-1]
        elif len(arr) == 2:
            arr[-2] = arr[-1]
            arr[-1] = -1
            return arr
        else:
            res = [0] * len(arr)
            res[-2] = arr[-1]
            res[-1] = -1
            for i in reversed(range(len(arr)-2)):
                if arr[i+1] > res[i+1]:
                    res[i] = arr[i+1]
                else:
                    res[i] = res[i+1]
            return res

时间复杂度$O(n)$，空间复杂度$O(n)$，运行结果：

改进：不用新开列表，用一个变量temp存储当前位置的元素，在原列表上修改，把空间复杂度降为$O(1)$，代码为：

python">class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        if len(arr) == 1:
            return [-1]
        elif len(arr) == 2:
            arr[-2] = arr[-1]
            arr[-1] = -1
            return arr
        else:
            temp = arr[-2]
            s = 0
            arr[-2] = arr[-1]
            arr[-1] = -1
            for i in reversed(range(len(arr)-2)):
                if temp > arr[i+1]:
                    s = arr[i]
                    arr[i] = temp
                    temp = s
                else:
                    temp = arr[i]
                    arr[i] = arr[i+1]
            return arr

自己解法：Python切片

利用max函数和切片可以直接得出结果，但时间效果不好

python">class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        for i in range(len(arr)-1):
            arr[i] = max(arr[i+1:])
        arr[-1] = -1
        return arr

官方解法

与我的第一种解法一样，也是倒序比较，参考：https://leetcode-cn.com/problems/replace-elements-with-greatest-element-on-right-side/solution/