[Leetcode] 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 <= 104
• 1 <= arr[i] <= 105

 

[ 내 코드 ]

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr)
    {
		size_t size = arr.size();
		int localMax = -1;

		for (int i = size - 1; i >= 0; i--)
		{
			int tmpValue = arr[i];
			arr[i] = localMax;

			localMax = std::max(localMax, tmpValue);
		}

		return arr;
    }
};

- 따로 max 함수를 구현해도 되지만, std::max를 쓰면 된다.

- 오른쪽부터 계산하면 O(N)으로 폴 수 있다. 배열 관련 문제가 나오면 반대 순서로 탐색하는 방법도 생각해 볼 수 있도록 해야 할 듯.