LeetCode 5134. 将每个元素替换为右侧最大元素 Replace Elements with Greatest Element on Right Side

地址 https://leetcode-cn.com/problems/replace-elements-with-greatest-element-on-right-side/

题目描述
给你一个数组 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;
}

};

 

版权声明：本文为itdef原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/itdef/p/12118211.html