Go语言实现LeetCode 1299：将每个元素替换为右侧最大元素

题目解析

给定一个数组 arr，要求将每个元素替换为其右侧最大的元素。对于数组中的最后一个元素，由于右侧没有元素，应将其替换为 -1。

示例 1：

• 输入：[17,18,5,4,6,1]
• 输出：[18,6,6,6,1,-1]
• 解释：
  - 下标 0 的元素 (17) → 右侧最大值是下标 1 的元素 (18)
  - 下标 1 的元素 (18) → 右侧最大值是下标 4 的元素 (6)
  - 下标 2, 3 的元素 → 右侧最大值均为 6
  - 下标 4 的元素 (6) → 右侧最大值是 1
  - 下标 5 的元素 (1) → 右侧无元素，替换为 -1

算法思路

若从左向右遍历计算每个元素右侧的最大值，需要重复扫描后续数组，导致时间复杂度达到 O(n²)。为了优化性能，可以采用逆向思维，即从右向左遍历数组。

在逆序遍历过程中，我们只需要记录当前已经遍历过的区域（即原数组中当前元素右侧的区域）中的最大值。随着遍历的进行，逐步更新这个最大值即可。这种方法可以将时间复杂度降至 O(n)，且无需额外数组存储结果，空间复杂度为 O(1)。

第1步：初始化变量

定义一个变量 max_val 用于记录右侧最大值。初始时，因为最后一个元素右侧没有数据，所以该变量初始化为 -1。

第2步：逆序遍历与替换

从数组的倒数第二个元素开始向前遍历（索引 i = len(arr)-2 至 0）。在每次迭代中：

1. 暂存当前值：使用临时变量保留当前 arr[i] 的值，因为该位置即将被覆盖。
2. 执行替换：将 arr[i] 更新为当前的 max_val。
3. 更新最大值：检查刚才暂存的旧值是否大于 max_val，若是，则更新 max_val 为新的最大值。

Go 语言实现

以下 Go 语言代码实现了上述逻辑。它直接修改传入的切片，并在遍历结束后返回结果，保持了优秀的内存效率。

func replaceElements(arr []int) []int {
	// 最后一个元素始终替换为 -1
	arr[len(arr)-1] = -1
	
	// max_val 记录从最右侧到当前位置之间（不含当前位置）的最大值
	max_val := arr[len(arr)-1] // 注意：这里其实需要先保存原始尾元素或直接用-1逻辑判断，更严谨的做法如下：
	// 修正逻辑：直接从右往左扫，max_val初始代表i+1到末尾的最大值。
	// 最简单的写法是维持一个右侧最大值的累积量
	
	return arr // 此处理论上需完整循环，见下方完善代码块
}

// 完善版：直接在循环外封装好逻辑
func replaceElementsOptimized(arr []int) []int {
	if len(arr) == 0 {
		return arr
	}
	
	maxVal := -1
	// 从后往前遍历
	for i := len(arr) - 1; i >= 0; i-- {
		temp := arr[i]
		arr[i] = maxVal
		if temp > maxVal {
			maxVal = temp
		}
	}
	
	return arr
}

关键点总结

• 逆向遍历是解决“右侧最大/最小值”类问题的常用技巧。
• 就地修改 (In-place)：利用临时变量暂存旧值，避免开辟新数组，节省空间。
• 边界条件：最后一个元素左侧没有右侧元素（或者说右侧为空），其对应的替换值为 -1，这符合初始化 maxVal = -1 的逻辑。

以上就是Go语言题解LeetCode1299将每个元素替换为右侧最大元素的详细内容，更多关于Go语言算法题的资料请关注本站其它相关文章！