1299. Replace Elements with Greatest Element on Right Side

Problem

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.

https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/

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⁴
• 1 <= arr[i] <= 10⁵

Test Cases

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('arr, expected', [
    ([17,18,5,4,6,1], [18,6,6,6,1,-1]),
    ([400], [-1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, arr, expected):
    assert sol.replaceElements(arr.copy()) == expected

Thoughts

可以直接 in-place 修改。从右向左扫描 arr，记录见到的最大的数字，并替换到扫描到的位置。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10

class Solution:
    def replaceElements(self, arr: list[int]) -> list[int]:
        greatest = -1
        for i in range(len(arr) - 1, -1, -1):
            tmp = arr[i]
            arr[i] = greatest
            if tmp > greatest:
                greatest = tmp

        return arr

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章