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 1:

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 index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Constraints:

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

Hint 1

Loop through the array starting from the end.

Hint 2

Keep the maximum value seen so far.

題目翻譯

這題是有一個整數陣列 arr，從開頭替換當前元素為右側中最大的元素，在最後一位的話替換成 -1。

解法解析

這題最好的解法就是搭配使用 In-place 的作法讓空間複雜度降低，但是有些程式語言不支援直接更新陣列的做法，例如 Rust 和 Swift。所以只能複製另一個陣列來操作。

這題雖然題目說從頭開始替換，但其實反向來做會是更好的方式。從尾部往頭部走，可以一邊替換一邊比較出右側的最大值，讓時間複雜度只需要 O(n) 即可。如果從頭部往尾部走，反而每走一步都要重新去找出右側最大值，複雜度會更高。

解法範例

Go

func replaceElements(arr []int) []int {
    mx := -1
    for i := len(arr) - 1; i >= 0; i-- {
        if arr[i] > mx {
            arr[i], mx = mx, arr[i]
        } else {
            arr[i] = mx
        }
    }
    return arr
}

JavaScript

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function (arr) {
    let mx = -1;
    for (let i = arr.length - 1; i >= 0; i--) {
        [arr[i], mx] = [mx, Math.max(arr[i], mx)];
    }
    return arr;
};

Kotlin

class Solution {
    fun replaceElements(arr: IntArray): IntArray {
        var mx: Int = -1
        for (i in arr.size - 1 downTo 0) {
            val tmp = arr[i]
            arr[i] = mx
            mx = maxOf(mx, tmp)
        }
        return arr
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $arr
     * @return Integer[]
     */
    function replaceElements($arr)
    {
        $mx = -1;
        for ($i = count($arr) - 1; $i >= 0; $i--) {
            $temp = $mx;
            $mx = max($arr[$i], $mx);
            $arr[$i] = $temp;
        }
        return $arr;
    }
}

Python

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

Rust

impl Solution {
    pub fn replace_elements(arr: Vec<i32>) -> Vec<i32> {
        let mut mx = -1;
        let mut res = vec![-1; arr.len()];
        for i in (0..arr.len()).rev() {
            res[i] = mx;
            mx = std::cmp::max(arr[i], mx);
        }
        res
    }
}

Swift

class Solution {
    func replaceElements(_ arr: [Int]) -> [Int] {
        var mx: Int = -1
        var res: [Int] = arr
        for i in (0..<arr.count).reversed() {
            res[i] = mx
            mx = max(mx, arr[i])
        }
        return res
    }
}