leetcode 1299 :要素を右側の最大要素と置き換える

この問題はthe Introduction to Data Structures Arrays-101 section leetcodeで.

問題声明
配列arr ,そして、その配列のすべての要素をその要素の中で最大の要素とし、その右側の要素を1 .
その後、配列を返します.
例1 :

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

制約

1 <= arr . length <= 10 ^ 4

1 <= arr [ i ] <= 10 ^ 5

解決1:2つのループ

var replaceElements = function(arr) {
    let newArr = []
    for(let i=0; i<arr.length; i++){    
        let max = arr[i+1]
        for(let j=i+1;j<arr.length;j++){
            let value = arr[j+1]
        max = value > max? value: max
        }
        newArr.push(max)
    }
    newArr[arr.length-1] = -1
    return newArr
};

時間複雑性:O(n‐ξ)
空間の複雑さ: O ( n )

解決2:1つのループ
最後のインデックスを- 1とすると、右側の要素から始まり、左側に1つずつ移動し、最大要素を追跡できます.すべての要素を最大要素に置き換えます.
例えば、
ARR =[ 17 , 18 , 5 , 4 , 6 , 1 ]
そして私たちが知っているように

NEWARR [ 5 ]は- 1です

NEWARR [ 4 ]はARR [ 5 ]に等しいです

NEWARR [ 3 ]はARR [ 4 ]からARR [ 5 ]の間の最大数に等しいです.これはarr [ 4 ]からnewarr [ 4 ]までの最大数に等しい

論理を簡単にするには、次のように記述できます:

newArr[0] = max(arr[1:5]) = max(arr[1], newArr[1])
newArr[1] = max(arr[2:5]) = max(arr[2], newArr[2])
newArr[2] = max(arr[3:5]) = max(arr[3], newArr[3])
newArr[3] = max(arr[4:5]) = max(arr[4], newArr[4])
newArr[4] = arr[5]
newArr[5] = -1

解決策は次のようになります.

var replaceElements = function(arr) {
    let newArr = [];
    newArr[arr.length-1] = -1;
    for (i = arr.length-2; i >= 0; i--) {
        newArr[i] = Math.max(newArr[i+1],arr[i+1]);
    }
    return newArr;
};

時間複雑性:O(n)
空間の複雑さ: O ( n )