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

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

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

Output: [18,6,6,6,1,-1]

Explanation:

• index 0 --> the greatest element to the right of index 0 is index 1 (18).
• index 1 --> the greatest element to the right of index 1 is index 4 (6).
• index 2 --> the greatest element to the right of index 2 is index 4 (6).
• index 3 --> the greatest element to the right of index 3 is index 4 (6).
• index 4 --> the greatest element to the right of index 4 is index 5 (1).
• index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]

Output: [-1]

Explanation: There are no elements to the right of index 0.

Constraints:

• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^5

题目大意

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入： arr = [17,18,5,4,6,1]

输出：[18,6,6,6,1,-1]

解释：

• 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
• 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
• 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
• 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
• 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
• 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入： arr = [400]

输出：[-1]

解释： 下标 0 的元素右侧没有其他元素。

提示：

• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^5

解题思路

1. 定义变量 max 记录右侧的最大值，初始化为 -1。
2. 定义变量 cur 记录右侧相邻元素的值，以免从右往左更新数组时被覆盖无法得到原始值，初始化为 -1。
3. 从数组的末尾向前遍历：
   • 更新 max 为 Math.max(max, cur)，此时 cur 是右侧相邻元素的值。
   • 临时存储当前元素到 cur。
   • 更新当前元素为 max。
4. 遍历结束，返回修改后的数组。

复杂度分析

• 时间复杂度：O(n)，只需从右向左遍历数组一次。
• 空间复杂度：O(1)，只使用了常量额外空间。

代码

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function (arr) {
	const n = arr.length;
	let max = -1,
		cur = -1;
	for (let i = n - 1; i >= 0; i--) {
		max = Math.max(cur, max);
		cur = arr[i];
		arr[i] = max;
	}
	return arr;
};

相关题目

题号	标题	题解	标签	难度	力扣
2078	两栋颜色不同且距离最远的房子	[✓]	贪心 数组	🟢	🀄️ 🔗
2454	下一个更大元素 IV		栈 数组 二分查找 3+	🔴	🀄️ 🔗