# LeetCode Solution, Easy, 1299. Replace Elements with Greatest Element on Right Side

# [1299. Replace Elements with Greatest Element on Right Side](https://leetcode.com/problems/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

```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

```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

```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

```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

```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

```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

```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
    }
}
```