LeetCode: 1299 Replace Elements with Greatest Element on Right Side

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

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 17 is 18.
- Index 1 → The greatest element to the right of 18 is 6.
- Index 2 → The greatest element to the right of 5 is 6.
- Index 3 → The greatest element to the right of 4 is 6.
- Index 4 → The greatest element to the right of 6 is 1.
- Index 5 → Replace 1 with -1 since it's the last element.

问题

给定一个数组 arr，将数组中的每个元素替换为其右边元素中的最大值，并将最后一个元素替换为 -1。
替换后返回该数组。

例子

输入: arr = [17,18,5,4,6,1]
输出: [18,6,6,6,1,-1]
解释: 
- 索引 0 → 17 右边的最大元素是 18。
- 索引 1 → 18 右边的最大元素是 6。
- 索引 2 → 5 右边的最大元素是 6。
- 索引 3 → 4 右边的最大元素是 6。
- 索引 4 → 6 右边的最大元素是 1。
- 索引 5 → 将 1 替换为 -1，因为它是最后一个元素。

Solution

Approach: Reverse Iteration / 反向迭代

We can solve this problem by iterating through the array in reverse.
We maintain a variable max_right to keep track of the maximum element to the right of the current index, updating it as we move from right to left.

Approach Explanation / 方法解释

Initialize max_right: We initialize max_right as -1 because the last element should be replaced by -1.
Iterate in Reverse: Start from the second-to-last element and move leftwards, updating the element with max_right and updating max_right if the current element is larger.
Final Replacement: Replace each element with the current max_right as we iterate, ensuring the maximum value to the right is tracked correctly.

Algorithm / 算法

Initialize max_right = -1.
Iterate from the last element to the first.
For each element, store the current value, replace it with max_right, and update max_right if the stored value is greater.

Implementation / 实现

Python

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_right = -1

        # Iterate from the end of the array to the beginning
        for i in range(len(arr) - 1, -1, -1):
            # Store the current element before replacing it
            current = arr[i]
            # Replace the current element with the maximum element to the right
            arr[i] = max_right
            # Update max_right if the current element is larger
            max_right = max(max_right, current)

        return arr

Explanation / 解释

Initialize max_right / 初始化 max_right
```
max_right = -1
```
- English: We initialize max_right as -1 because the last element of the array must be replaced by -1.
- Chinese: 我们将 max_right 初始化为 -1，因为数组的最后一个元素必须替换为 -1。
Iterate in Reverse / 反向迭代
```
for i in range(len(arr) - 1, -1, -1):
```
- English: We loop through the array from right to left, starting from the last element.
- Chinese: 我们从右向左遍历数组，从最后一个元素开始。
Replace and Update / 替换并更新
```
current = arr[i]
arr[i] = max_right
max_right = max(max_right, current)
```
- English: For each element, we store the current value in current, replace it with max_right, and then update max_right if the current value is larger.
- Chinese: 对于每个元素，我们将当前值存储在 current 中，将其替换为 max_right，然后如果当前值更大则更新 max_right。
Return the Updated Array / 返回更新后的数组
```
return arr
```
- English: Return the modified array after the loop completes.
- Chinese: 在循环完成后返回修改后的数组。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of elements in the array. We iterate through the array once.
Space Complexity / 空间复杂度: O(1), since we only use a constant amount of extra space for max_right.

Key Concept / 关键概念

Reverse Iteration / 反向迭代: Iterating from right to left allows us to keep track of the maximum value to the right of each element and efficiently update the array in-place.
In-Place Modification / 就地修改: By updating the array as we go, we avoid the need for additional space beyond a single variable.

Summary / 总结

English: To replace elements with the greatest value to their right, we can use reverse iteration to efficiently track the maximum value and update the array in-place.
Chinese: 要将每个元素替换为其右边的最大值，我们可以使用反向迭代来高效跟踪最大值并就地更新数组。

Tips / 提示

English: Practice reverse iteration techniques, as they are useful in problems where future values (like elements to the right) need to influence current decisions.
Chinese: 练习反向迭代技巧，因为它们在需要未来值（如右侧的元素）影响当前决策的问题中非常有用。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice reverse iteration and in-place modification problems to improve your understanding of space optimization techniques.
Chinese: 练习反向迭代和就地修改问题，以提高你对空间优化技术的理解。

Post Views: 13

CODEBITWAVE