1299-将每个元素替换为右侧最大元素

给你一个数组 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 <= 104
• 1 <= arr[i] <= 105

方法一：逆序遍历

本题等价于对于数组 arr 中的每个元素 arr[i]，将其替换成 arr[i + 1], arr[i + 2], ..., arr[n - 1] 中的最大值。因此我们可以逆序地遍历整个数组，同时维护从数组右端到当前位置所有元素的最大值。

设 ans[i] = max(arr[i + 1], arr[i + 2], ..., arr[n - 1])，那么在进行逆序遍历时，我们可以直接通过

ans[i] = max(ans[i + 1], arr[i + 1])

来递推地得到答案。

[sol1-C++]

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n);
        ans[n - 1] = -1;
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = max(ans[i + 1], arr[i + 1]);
        }
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        ans = [0] * (n - 1) + [-1]
        for i in range(n - 2, -1, -1):
            ans[i] = max(ans[i + 1], arr[i + 1])
        return ans

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组 arr 的长度。

• 空间复杂度：O(1)，除了存储答案的数组 ans 之外，额外的空间复杂度是 O(1)。