LeetCode 题解工作台
将每个元素替换为右侧最大元素
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。 完成所有替换操作后，请你返回这个数组。 示例 1： 输入： arr = [17,18,5,4,6,1] 输出： [18,6,6,6,1,-1] 解释： - 下标 0 的元素 --> 右侧最大元素是下标…
1
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们用一个变量 记录当前位置右侧的最大值，初始时 $mx = -1$。 然后我们从右向左遍历数组，对于每个位置 ，我们记当前位置的值为 ，将当前位置的值更新为 ，然后更新 $mx = \max(mx, x)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个数组 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 <= 1041 <= arr[i] <= 105
解题思路
方法一：逆序遍历
我们用一个变量 记录当前位置右侧的最大值，初始时 。
然后我们从右向左遍历数组，对于每个位置 ，我们记当前位置的值为 ，将当前位置的值更新为 ，然后更新 。
最后返回原数组即可。
时间复杂度 ，其中 为数组长度。空间复杂度 。
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
mx = -1
for i in reversed(range(len(arr))):
x = arr[i]
arr[i] = mx
mx = max(mx, x)
return arr
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests understanding of array traversal and modification in-place.
- question_mark
Checks if the candidate is aware of optimizing both time and space complexities.
- question_mark
Assesses ability to handle edge cases like single-element arrays and no right elements.
常见陷阱
外企场景- error
Not accounting for the last element, which must be replaced with -1.
- error
Confusing the order of operations when updating the elements from right to left.
- error
Using unnecessary extra space when the problem can be solved in-place.
进阶变体
外企场景- arrow_right_alt
Handling arrays with only one element.
- arrow_right_alt
Modifying the problem to work with arrays of floating-point numbers.
- arrow_right_alt
Implementing the solution with additional constraints such as negative numbers.