将每个元素替换为右侧最大元素
难度:
标签:
题目描述
代码结果
运行时间: 51 ms, 内存: 16.8 MB
/*
思路:
Java Stream 不适合直接处理这种具有状态依赖的替换问题。我们可以先用 Stream 处理数组,再结合传统循环完成替换。
*/
import java.util.stream.IntStream;
public class Solution {
public int[] replaceElements(int[] arr) {
int n = arr.length;
int[] result = IntStream.of(arr).toArray();
int maxFromRight = -1;
for (int i = n - 1; i >= 0; i--) {
int current = result[i];
result[i] = maxFromRight;
if (current > maxFromRight) {
maxFromRight = current;
}
}
return result;
}
}
解释
方法:
此题解采用从右向左遍历的方式。在遍历过程中,使用一个变量max_num来记录当前遍历到的元素右侧的最大值。对于数组中的每个元素,我们将其替换为max_num,然后更新max_num为当前元素和max_num中的较大值。这样可以保证max_num始终是当前元素右侧的最大值。遍历完成后,数组中的每个元素都被替换为其右侧的最大元素。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在此题解中,为什么选择从右向左而不是从左向右进行遍历来实现该算法?
▷🦆
在算法中,`max_num` 初始化为负无穷大的原因是什么?
▷🦆
该算法中有提到使用`tmp`变量,`tmp`变量的具体作用是什么?
▷🦆
最后一个元素为什么总是被替换为-1,这里的逻辑是怎样的?
▷