标签: 数组
难度: Easy
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1] 解释： - 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18) - 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1) - 下标 5 的元素 --> 右侧没有其他元素，替换为 -1
示例 2：
输入：arr = [400] 输出：[-1] 解释：下标 0 的元素右侧没有其他元素。
提示：
1 <= arr.length <= 1041 <= arr[i] <= 105运行时间: 51 ms
内存: 16.8 MB
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
n = len(arr)
tmp = -1
max_num = float('-inf')
for i in range(n - 1 ,-1, -1):
if max_num <= tmp:
max_num = tmp
tmp = arr[i]
arr[i] = max_num
return arr
此题解采用从右向左遍历的方式。在遍历过程中，使用一个变量max_num来记录当前遍历到的元素右侧的最大值。对于数组中的每个元素，我们将其替换为max_num，然后更新max_num为当前元素和max_num中的较大值。这样可以保证max_num始终是当前元素右侧的最大值。遍历完成后，数组中的每个元素都被替换为其右侧的最大元素。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
n = len(arr)
tmp = -1 # 用于暂存当前元素
max_num = float('-inf') # 初始化最大值为负无穷
for i in range(n - 1, -1, -1): # 从右向左遍历
if max_num <= tmp:
max_num = tmp # 更新max_num为右侧的最大值
tmp = arr[i] # 更新tmp为当前元素
arr[i] = max_num # 将当前元素替换为右侧最大值
return arr
选择从右向左遍历是因为算法需要将每个元素替换为其右侧的最大元素。如果从左向右遍历，我们需要在遍历过程中不断记录右侧所有元素的最大值，这通常需要额外的数据结构如数组来存储每个位置右侧的最大值，增加了空间复杂度。从右向左遍历则可以实时更新当前的最大值，并直接在原数组上进行修改，简化了实现并减少了空间使用。
在算法中，`max_num` 初始化为负无穷大是为了确保在遍历开始时，任何一个实际存在的元素都大于`max_num`。这样可以保证第一次比较时能够正确地将`max_num`更新为数组中的实际元素。随着遍历的进行，`max_num`会不断更新为遇到的最大值，从而正确地替换每个元素。
`tmp`变量在算法中用于暂存当前遍历到的元素。这是必要的，因为在将当前位置的元素更新为右侧的最大值之前，需要保留当前元素的值，以便在下一次迭代时可以用这个值来更新`max_num`。如果不使用`tmp`来暂存这个值，当前元素的原始值将会丢失，导致无法正确地更新`max_num`。
在题解中，遍历到最后一个元素时（即数组最右侧元素），其右侧没有其他元素，因此按题目要求，这个位置应该被替换为右侧最大元素的值。但由于其右侧没有元素，最大元素的值理论上不存在。题目规定在这种情况下应该用-1来替代，表示右侧没有更大的元素。因此，算法在处理到数组的最后一个元素时直接将其替换为-1。