LeetCode 解題練習：Replace Elements with Greatest Element on Right Side

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

中文描述

給定一個整數陣列 arr，將每個元素用該元素的右邊所有元素中之最大值來取代，並將最後一個元素用-1取代。

範例一：

輸入  arr = [45, 333, 2, 1, 9, 17]

輸出 [333, 17, 17, 17, 17, -1]

因為 45 右邊元素 [333, 2, 1, 9, 17] 最大值為 333。

因為 333 右邊元素 [2, 1, 9, 17] 最大值為 17。

因為 2 右邊元素 [1, 9, 17] 最大值為 17。

因為 1 右邊元素 [9, 17] 最大值為 17。

因為 9 右邊元素 [17] 最大值為 17。

範例二：

輸入  arr = [333]

輸出 [-1]

 

解法：

以 curMax = -1 當目前最大值，t暫存目前陣列元素。從陣列的右邊開始以curMax替代，若 t 大於 curMax，則更新 curMax 為 t。

可參考底下圖片動畫說明：

Python Code

class Solution:

    def replaceElements(self, arr: List[int]) -> List[int]:

        curMax = -1 # 目前最大值

        for i in range(len(arr)-1, -1, -1): # 從右邊開始替代

            t = arr[i] # 暫存目前陣列元素

            arr[i] = curMax # 以目前最大值替代陣列元素

            if t > curMax: # 若此陣列元素比目前最大值大

                curMax = t # 更新目前最大值

       

        return arr