题目描述

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

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

示例:

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

提示:

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

解法 1:反向遍历

从尾到头遍历即可,这里要注意是「用它右边最大的元素替换」,不包括该元素自身

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        if len(arr) == 0:
            return []
        max_val = arr[-1]
        for i in range(len(arr) - 2, -1, -1):
            arr[i], max_val = max_val, max(max_val, arr[i])
        arr[-1] = -1
        return arr
  • 执行用时:104 ms,在所有 Python3 提交中击败了 66.07% 的用户。
  • 内存消耗:14.6 MB,在所有 Python3 提交中击败了 14.29% 的用户。