题目描述

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

提示：

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

样例

示例：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]

算法1

逆序计算 记录右边最大值 本次替换使用
还要记录加入当前数组后的最大值 下次替换使用
最后 数组末尾填充-1

时间复杂度 O(n)

C++ 代码

class Solution {
public:

    vector<int> replaceElements(vector<int>& arr) {
    int currMax = -1; int preMax = -1;
    for (int i = arr.size() - 1; i >= 0; i--) {
        if (i == arr.size() - 1) {
            currMax = arr[i];
            preMax = arr[i];
            continue;
        }
        preMax = currMax;
        currMax = max(arr[i], currMax);
        arr[i] = preMax;
    }
    arr.back() = -1;

    return arr;
}

};