LeetCode1299

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; // 返回结果数组 } }

---

总结

这段代码通过从右向左遍历数组，并动态更新右侧的最大值，能够更高效地解决问题。