【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 <= 104
• 1 <= arr[i] <= 105

解題方法：模擬

使用一個變量M記錄右邊元素最大值，初始值為-1。

從后向前遍歷數組，使用nextM記錄遍歷完這個元素之后的最大值（nextM = max(arr[i], M)），更新這個元素為M，并更新M為nextM。

最終返回arr即為答案。

• 時間復雜度$O(len(arr))$
• 空間復雜度$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:vector<int> replaceElements(vector<int>& 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:15
'''
from 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 arr

Java

/** @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和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源

Tisfy：https://blog.letmefly.xyz/2025/02/16/LeetCode 1299.將每個元素替換為右側最大元素/