自助建站系统步骤,建立网站的注意事项,上海网站建设方案策划,上贵州省建设厅的网站【LetMeFly】1299.将每个元素替换为右侧最大元素#xff1a;倒序遍历#xff0c;维护最大值#xff0c;原地修改
力扣题目链接#xff1a;https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/
给你一个数组 arr #xff0c;请你将每个…【LetMeFly】1299.将每个元素替换为右侧最大元素倒序遍历维护最大值原地修改
力扣题目链接https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/
给你一个数组 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 1041 arr[i] 105
解题方法模拟
使用一个变量M记录右边元素最大值初始值为-1。
从后向前遍历数组使用nextM记录遍历完这个元素之后的最大值nextM max(arr[i], M)更新这个元素为M并更新M为nextM。
最终返回arr即为答案。
时间复杂度 O ( l e n ( a r r ) ) O(len(arr)) O(len(arr))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
/** Author: LetMeFly* Date: 2025-02-16 10:21:04* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-16 10:22:18*/
class Solution {
public:vectorint replaceElements(vectorint arr) {int M -1;for (int i arr.size() - 1; i 0; i--) {int nM max(M, arr[i]);arr[i] M;M nM;}return arr;}
};Python Author: LetMeFly
Date: 2025-02-16 10:21:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-16 10:23:15from typing import Listclass Solution:def replaceElements(self, arr: List[int]) - List[int]:M -1for i in range(len(arr) - 1, -1, -1):arr[i], M M, max(arr[i], M)return arrJava
/** Author: LetMeFly* Date: 2025-02-16 10:21:15* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-16 10:24:13*/
class Solution {public int[] replaceElements(int[] arr) {int M -1;for (int i arr.length - 1; i 0; i--) {int nM Math.max(M, arr[i]);arr[i] M;M nM;}return arr;}
}Go
/** Author: LetMeFly* Date: 2025-02-16 10:21:19* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-16 10:26:54*/
package mainfunc max_REWGEORS(a, b int) int {if a b {return a}return b
}func replaceElements(arr []int) []int {M : -1for i : len(arr) - 1; i 0; i-- {nM : max_REWGEORS(arr[i], M)arr[i] MM nM}return arr
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ 千篇源码题解已开源 Tisfyhttps://blog.letmefly.xyz/2025/02/16/LeetCode 1299.将每个元素替换为右侧最大元素/
