leetcode
leetcode 1051 ~ 1100
将每个元素替换为右侧最大元素

将每个元素替换为右侧最大元素

难度:

标签:

题目描述

代码结果

运行时间: 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` 初始化为负无穷大的原因是什么?
在算法中,`max_num` 初始化为负无穷大是为了确保在遍历开始时,任何一个实际存在的元素都大于`max_num`。这样可以保证第一次比较时能够正确地将`max_num`更新为数组中的实际元素。随着遍历的进行,`max_num`会不断更新为遇到的最大值,从而正确地替换每个元素。
🦆
该算法中有提到使用`tmp`变量,`tmp`变量的具体作用是什么?
`tmp`变量在算法中用于暂存当前遍历到的元素。这是必要的,因为在将当前位置的元素更新为右侧的最大值之前,需要保留当前元素的值,以便在下一次迭代时可以用这个值来更新`max_num`。如果不使用`tmp`来暂存这个值,当前元素的原始值将会丢失,导致无法正确地更新`max_num`。
🦆
最后一个元素为什么总是被替换为-1,这里的逻辑是怎样的?
在题解中,遍历到最后一个元素时(即数组最右侧元素),其右侧没有其他元素,因此按题目要求,这个位置应该被替换为右侧最大元素的值。但由于其右侧没有元素,最大元素的值理论上不存在。题目规定在这种情况下应该用-1来替代,表示右侧没有更大的元素。因此,算法在处理到数组的最后一个元素时直接将其替换为-1。

相关问题