LeetCode 1299. 将每个元素替换为右侧最大元素
题目描述
题意分析
把每个位置替换成原数组中严格位于它右侧的最大值，不能把当前元素本身算进去。最后一个元素右侧为空，按题意写成
-1，并返回修改后的数组。相邻位置所需的信息只差一个元素：知道原数组
[i + 1, n)的最大值，再加入原来的arr[i]，就能得到下一个待处理位置所需的最大值，因此从右向左扫描最方便。
解法：从右向左维护最大值
核心思路
[!blue]
用
rightMax保存已处理后缀中原始元素的最大值。进入位置i时，它对应的范围恰好是严格右侧[i + 1, n)，所以可以直接作为arr[i]的新值。但原来的
arr[i]还会影响左侧位置的答案，覆盖前必须先保存到cur。然后写入rightMax，最后用cur更新最大值；更新后的范围扩展为原数组[i, n)，正好供下一轮使用。这个顺序既排除了当前元素自身，也保留了后续需要的原值。右边已经改写的数组内容不再读取，只使用维护好的最大值，因此可以安全地原地覆盖。
初始
rightMax = -1，让末项自然得到题目要求的值。题目中的原始元素均为正数，第一次合并原值后，-1就不会干扰非空后缀的最大值。
解题步骤
- 初始化
rightMax = -1，从末尾下标开始倒序遍历。- 用
cur保存当前元素的原值，再把rightMax写入当前位置。- 若
cur > rightMax，更新最大值，随后继续处理左边的位置。- 包括下标
0在内的所有位置处理完后，返回原数组。单元素数组只执行一轮，结果就是[-1]。
代码实现
class Solution {
public int[] replaceElements(int[] arr) {
int rightMax = -1;
for (int i = arr.length - 1; i >= 0; i--) {
// 先保存将被覆盖的原值，它还要参与左边位置的答案。
int cur = arr[i];
// 先写严格右侧最大值，再把当前原值并入范围。
arr[i] = rightMax;
if (cur > rightMax) {
rightMax = cur;
}
}
return arr;
}
}
func replaceElements(arr []int) []int {
rightMax := -1
for i := len(arr) - 1; i >= 0; i-- {
// 先保存将被覆盖的原值，它还要参与左边位置的答案。
cur := arr[i]
// 先写严格右侧最大值，再把当前原值并入范围。
arr[i] = rightMax
if cur > rightMax {
rightMax = cur
}
}
return arr
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 写入前，
rightMax对应严格右侧；更新后，它才包含当前原值。- 最大值累计的是原值，不是已替换的新值。
易错点总结
[!yellow]
- 先更新最大值再写，会把当前项也算入自身答案。
- 覆盖后才读取原值，会使最大值无法正确推进。
- 只遍历到下标一，会漏掉第一项，循环条件必须包含
i == 0。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 238. 除了自身以外数组的乘积 | 中等 | 同样从后向前累计后缀信息，本题取最大值，原题累计乘积并与前缀组合。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！