1299. 将每个元素替换为右侧最大元素（简单）- LeetCode

在这里插入图片描述
注意这里的右边不包括该位置上的元素。

自己解法：动态规划

设新列表为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