当前位置：首页 > article >正文

LeetCode1299

article 2025/2/21 23:25:20

LeetCode1299

题目描述

给你一个数组 arr，请你将每个元素替换为它右侧最大的元素。如果右侧没有元素，则替换为 -1。

完成替换操作后，返回这个数组。

示例

示例 1

输入:

arr = [17, 18, 5, 4, 6, 1]

输出:

[18, 6, 6, 6, 1, -1]

解释:

下标 0 的元素右侧最大元素是 18。
下标 1 的元素右侧最大元素是 6。
下标 2 的元素右侧最大元素是 6。
下标 3 的元素右侧最大元素是 6。
下标 4 的元素右侧最大元素是 1。
下标 5 的元素右侧没有元素，替换为 -1。

示例 2

输入:

arr = [400]

输出:

[-1]

解释:

下标 0 的元素右侧没有元素，替换为 -1。

思路分析

问题核心

我们需要将数组中的每个元素替换为它右侧最大的元素。如果右侧没有元素，则替换为 -1。

思路拆解

从右向左遍历：
- 从数组的末尾开始遍历，可以方便地记录当前元素右侧的最大值。
更新最大值：
- 在遍历过程中，用一个变量 max 记录当前元素右侧的最大值。
- 每次更新当前元素为 max，然后更新 max 为当前元素和 max 中的较大值。
处理边界条件：
- 最后一个元素右侧没有元素，直接替换为 -1。

代码段

class Solution {
    public int[] replaceElements(int[] arr) {
        int max = -1;
        int len = arr.length;
        for (int i = len - 1; i >= 0; i--) {
            int temp = arr[i];
            arr[i] = max;
            max = Math.max(max, temp);
        }
        return arr;
    }
}

在这里插入图片描述

代码逐行讲解

1. 初始化最大值

int max = -1;

max 用于记录当前元素右侧的最大值，初始值为 -1。

2. 获取数组长度

int len = arr.length;

len 是数组的长度，用于控制遍历的范围。

3. 从右向左遍历

for (int i = len - 1; i >= 0; i--) {

从数组的最后一个元素开始，向左遍历到第一个元素。

4. 保存当前元素

int temp = arr[i];

temp 用于保存当前元素的值，以便后续更新 max。

5. 替换当前元素

arr[i] = max;

将当前元素替换为 max，即右侧的最大值。

6. 更新最大值

max = Math.max(max, temp);

更新 max 为当前元素和 max 中的较大值。

7. 返回结果数组

return arr;

返回替换后的数组。

复杂度分析

时间复杂度

我们只需要遍历数组一次，因此时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度

只使用了常数级别的额外空间，因此空间复杂度为 O(1)。

总结的知识点

1. 数组遍历

从右向左遍历数组，可以方便地记录右侧的最大值。

2. 变量更新

使用 max 变量记录当前最大值，并在遍历过程中动态更新。

3. 边界条件处理

最后一个元素右侧没有元素，直接替换为 -1。

整合

class Solution {
    public int[] replaceElements(int[] arr) {
        int max = -1; // 初始化最大值
        int len = arr.length; // 数组长度
        for (int i = len - 1; i >= 0; i--) { // 从右向左遍历
            int temp = arr[i]; // 保存当前元素
            arr[i] = max; // 将当前元素替换为右侧最大值
            max = Math.max(max, temp); // 更新最大值
        }
        return arr; // 返回结果数组
    }
}