Easy

题目描述

给定一个数组 arr，将数组中的每个元素替换为其右侧所有元素中的最大值，并将最后一个元素替换为 -1。

完成后返回该数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 索引 0 --> 索引 0 右侧最大元素是索引 1 处的 18
- 索引 1 --> 索引 1 右侧最大元素是索引 4 处的 6  
- 索引 2 --> 索引 2 右侧最大元素是索引 4 处的 6
- 索引 3 --> 索引 3 右侧最大元素是索引 4 处的 6
- 索引 4 --> 索引 4 右侧最大元素是索引 5 处的 1
- 索引 5 --> 索引 5 右侧没有元素，所以用 -1 替换

示例 2：

输入：arr = [400]
输出：[-1]
解释：索引 0 右侧没有元素

约束条件：

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

解题思路

这道题有两种常见解法：

方法一：双重循环（暴力解法） 对于每个位置，遍历其右侧所有元素找到最大值。时间复杂度为 O(n²)，空间复杂度为 O(1)。

方法二：从右到左遍历（推荐解法） 关键观察：如果我们从右到左遍历数组，可以在一次遍历中维护"右侧最大值"。

具体步骤：

  1. 从数组末尾开始向前遍历
  2. 用变量 maxRight 记录当前位置右侧的最大值
  3. 对于当前元素，先保存其值，然后将其替换为 maxRight
  4. 更新 maxRight 为保存的当前元素值和原 maxRight 的较大值
  5. 最后一个元素直接设为 -1

这种方法只需要一次遍历，时间复杂度为 O(n)，是最优解法。

代码实现

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

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_right = -1
        
        for i in range(len(arr) - 1, -1, -1):
            current = arr[i]
            arr[i] = max_right
            max_right = max(max_right, current)
        
        return arr

public class Solution {
    public int[] ReplaceElements(int[] arr) {
        int maxRight = -1;
        
        for (int i = arr.Length - 1; i >= 0; i--) {
            int current = arr[i];
            arr[i] = maxRight;
            maxRight = Math.Max(maxRight, current);
        }
        
        return arr;
    }
}

var replaceElements = function(arr) {
    let maxRight = -1;
    
    for (let i = arr.length - 1; i >= 0; i--) {
        let current = arr[i];
        arr[i] = maxRight;
        maxRight = Math.max(maxRight, current);
    }
    
    return arr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度最优解法（从右到左）暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(1)O(1)

其中 n 为数组长度。最优解法只需要一次遍历和常数额外空间。

相关题目