LeetCode 1299. Replace Elements with Greatest Element on Right Side 用右侧的最大元素替换元素 (Easy)

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.
给定一个数组arr，用其右边元素中最大的元素替换该数组中的每个元素，并用-1替换最后一个元素。

After doing so, return the array.
这样做之后，返回数组。

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

Constraints:

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

Solution:

#solution 1 - forward
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        for i in range(len(arr)-1):
            arr[i] = max(arr[i+1:])
        arr[-1] = -1
        return arr

This solution is straightforward but relatively slow. Just keep in mind that max() doesn t take empty sequence for the its argument. So we need to loop to the len(arr)-1该解决方案很简单，但是相对较慢。需要补充的一点是，max（）的参数不接受空序列。所以需要loop到len(arr) – 1。

#solution 2 - backward
class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        max_num = -1
        i = len(arr) - 1
        while i >= 0 :
            temp = arr[i]
            arr[i] = max_num
            if temp > max_num :
                max_num  = temp
        i -= 1
        return arr 

If we think this from backward, then this question will become update the current value with the max value we have seen, which uses a variable to track the max, thus dramatically reducing the computation cost.
如果我们从反向思考，那么这个问题将变为使用我们看到的最大值来更新当前值，使用变量来跟踪见过的最大值，从而大大降低了计算成本。